問題文

正整数$N$が与えられます．$N \times N$行列$A$を以下のように定めます．

$A$の$(i,j)$成分を$A_{i,j}$と表す．

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

以下の問いに$Q$回答えてください．問$i$の形式は以下の通りです．

• $x_i,y_i(1 \leq x_i,y_i \leq N)$が与えられる．$A \times A$の$(x_i,y_i)$成分，つまり$A^2_{x_i,y_i}$を求めよ．

制約

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

入力

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

出力

答えを$Q$行に出力せよ．$i$行目には問$i$の答えを出力せよ．

サンプル

4
4
2 1
2 4
1 1
3 3

2
0
1
1

$A= \begin{pmatrix} 1 & 0 & 0 &0 \\ 1 & 1 & 0 &0 \\ 1 & 0 & 1 &0 \\ 1 & 1 & 0 &1 \\ \end{pmatrix}$ です． よって $A^2= \begin{pmatrix} 1 & 0 & 0 &0 \\ 2 & 1 & 0 &0 \\ 2 & 0 & 1 &0 \\ 3 & 2 & 0 &1 \\ \end{pmatrix}$です．

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

0
0
0
0
0
0
0
0
0
0