問題文


正整数が与えられます.行列を以下のように定めます.

成分をと表す.

  • で割り切れるとき
  • で割り切れないとき

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

  • が与えられる.成分,つまりを求めよ.

制約


  • 入力で与えられる値はすべて整数である

入力


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






出力


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

サンプル


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

です. よって です.

入力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.14)