C - (Many Queries)^{-1}

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

配点： 点

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

整数の変数 があり，はじめ です．

MojaMoja 君は 個のクエリを順に処理しました．
番目のクエリは以下です：

• の値を で置き換える．

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

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

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

• は整数
• 個のクエリを順に処理することで を得られるような非負整数 が存在する

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

答えを出力せよ．

1
363

5

のとき， の値は と推移します．

3
0
7016566358771
15664562761879

0
14142
31415