Who's Next ? [Hard]

2 secs 1024 MB
sgsw

問題文


(難易度目安 : 点)

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

例えば、

=

=

です。

自然数が与えられます。

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


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

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

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

制約


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

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

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

かつの要素である

入力


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

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

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

M
p q

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

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

出力


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

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

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

サンプル


入力1
4
2
1 2
6
4 5
7
2 3
6
3 5
出力1
1 1
5 6
5 7
2 3

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

入力2
4
726
45 188
885
181 205
305
169 282
62
37 41
出力2
152 635
626 709
172 287
28 31
入力3
4
705114717
590136178 616807693
400822285
8708089 86329833
808186475
236869257 466568537
394895154
99700898 208593159
出力3
415141047 433903565
35546168 352395887
238027112 468849199
139333797 291512689

提出


Go (1.14)