問題文

正整数NNが与えられます.N×NN \times N行列AAを以下のように定めます.

AA(i,j)(i,j)成分をAi,jA_{i,j}と表す.

  • iijjで割り切れるときAi,j=1A_{i,j}=1
  • iijjで割り切れないときAi,j=0A_{i,j}=0

以下の問いにQQ回答えてください.問iiの形式は以下の通りです.

  • xi,yi(1xi,yiN)x_i,y_i(1 \leq x_i,y_i \leq N)が与えられる.A×AA \times A(xi,yi)(x_i,y_i)成分,つまりAxi,yi2A^2_{x_i,y_i}を求めよ.

制約

  • 1N1061 \leq N \leq 10^6
  • 1Q1051 \leq Q \leq 10^5
  • 1xi,yiN1 \leq x_i,y_i \leq N
  • 入力で与えられる値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます.

NN
QQ
x1x_1y1y_1
x2x_2y2y_2
\vdots
xQx_QyQy_Q

出力

答えをQQ行に出力せよ.ii行目には問iiの答えを出力せよ.

サンプル

入力1
4
4
2 1
2 4
1 1
3 3
出力1
2
0
1
1

A=(1000110010101101)A= \begin{pmatrix} 1 & 0 & 0 &0 \\ 1 & 1 & 0 &0 \\ 1 & 0 & 1 &0 \\ 1 & 1 & 0 &1 \\ \end{pmatrix} です. よって A2=(1000210020103201)A^2= \begin{pmatrix} 1 & 0 & 0 &0 \\ 2 & 1 & 0 &0 \\ 2 & 0 & 1 &0 \\ 3 & 2 & 0 &1 \\ \end{pmatrix} です.

入力2
1000000
10
873930 407326
573419 416908
36023 290264
59455 62049
393215 235603
260609 88214
976337 630158
450140 309938
276091 634466
762854 398528
出力2
0
0
0
0
0
0
0
0
0
0

提出


Go (1.21)