Big Pattern Number

2 secs 1024 MB
OxOmiso

問題文


以上の整数 と, 以上の整数 が与えられます。
進法で,以下の条件を満たす整数を とします。 は一意に定まります。

  • を満たす について, の位が である。

さて, 進数で表された の, 進数での値を で割った余りで求めてください。
個のテストケースが与えられるので,それぞれについて答えを求めてください。

例として, のとき, となります。このとき, が求める答えであり, となり, が答えとなります。

作問者の想定解が誤っていました。制約を変更することで対応しました。申し訳ございません。


を, に変更しました。

制約




入力例 1


6
4 2
2 1 
10 5
4 10
3141592 65358979
1000000000 1000000000

出力例 1


58596
2
94746490
655820314
459742684
330625733

で割った余りを出力することを忘れないでください。

提出


Go (1.14)