01 Matrix 2

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

の成分をと表す．

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

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

• が与えられる．の成分，つまりを求めよ．

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

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

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

4
4
2 1
2 4
1 1
3 3

2
0
1
1

です． よって です．

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