概要

入力のパターンに限りがあるので，前計算をしておきましょう！

問題原案：tnodino
改題：uni_kakurenbo

解説

「非負 $k$ を無作為に選んだとき，$3^k \bmod 998244353$ の値は平均して $\frac{998244353}{2} \backsimeq 5 \times 10^8$ くらいになるだろう」という予想がつきます．(実際，$3$ は $998244353$ の原始根であるので正しいです．)

さらに，$5 \times 10^8 \times 10^5 > 2^{45} \backsimeq 3 \times 10^{13}$ であるので，だいたい答えは $10^5$ 以下程度には収まるのではないか，という予想も立てられます．

コードを書いて試してみると，実際に $q > 70436$ で $x \geq 2^{45}$ となることがわかります．

ですから，これらの値をすべて $\Phi$ 個のテストケースを処理する前に求めておいて，辞書などで保存しておくことで十分高速にこの問題を解決できることがわかります．

解説：uni_kakurenbo

実装例