Who's Next ? [Hard]

(難易度目安 : 点)

自然数が与えられた時、以上 以下であり、分母が以下であるような規約分数を小さい順に並べた結果得られる数列をと定義します。

例えば、

=

=

です。

自然数が与えられます。

以下の個のクエリに解答してください。

◎自然数と互いに素な自然数のペアが与えられる。

分数はの要素かつその番目の項であるとする。

の番目の要素をと表すとき、自然数のペアを求めよ。

・テストケースは個与えられる。

・

◉全てのテストケースに対して以下が成り立つ。

・入力はすべて正の自然数

・

・かつはの要素である

はじめに = (テストケースの数)が与えられる。

その後回にわたって,番目のクエリが与えられる。

各クエリは以下の形式で与えられる。

M
p q

テストケース全体での入力は以下で与えられる。

T
M_1
p_1 q_1
M_2
p_2 q_2
.
.
.
M_T
p_T q_T

全部で行出力してください。

行目には、番目のクエリの自然数のペアを出力してください。

最後に改行してください。

4
2
1 2
6
4 5
7
2 3
6
3 5

1 1
5 6
5 7
2 3

つめのクエリにおいて、 = を見ると、の次はです。

4
726
45 188
885
181 205
305
169 282
62
37 41

152 635
626 709
172 287
28 31

4
705114717
590136178 616807693
400822285
8708089 86329833
808186475
236869257 466568537
394895154
99700898 208593159

415141047 433903565
35546168 352395887
238027112 468849199
139333797 291512689