マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$100$ 点

解説が見れないのでミラーを貼ります：Editorial

問題文

整数の変数 $x$ があり，はじめ $x = 0$ です．

MojaMoja 君は $q$ 個のクエリを順に処理しました．
$k \scriptsize \; (1 \leq k \leq q)$ 番目のクエリは以下です：

• $x$ の値を $x + (3^k \bmod 998244353)$ で置き換える．

また，$q$ 個のクエリをすべて処理した後，MojaMoja 君は $x$ の値を出力しました．

MojaMoja 君の出力した値は $X$ だったそうです．
$q$ を求めてください．

なお，この問題の制約において答えは一意に定まることを保証します．

制約

• $1 \leq \Phi \leq 10^5$
• $0 \leq X < \bold{2^{45}}$
• $X$ は整数
• $q$ 個のクエリを順に処理することで $x=X$ を得られるような非負整数 $q$ が存在する

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えを出力せよ．

サンプル

1
363

5

$q = 5$ のとき，$x$ の値は $0 \xrightarrow{+3^1} 3 \xrightarrow{+3^2} 12 \xrightarrow{+3^3} 39 \xrightarrow{+3^4} 120 \xrightarrow{+3^5} 363$ と推移します．

3
0
7016566358771
15664562761879

0
14142
31415