ノート

問題文

みなさん，数字を使った占いというものをご存知でしょうか?
0-9の数字で構成された数字列$S=\{ s_1,s_2,\dots,s_N \}$に対して以下の操作を行います．

1. 数字列$S$の長さを$K$とする．$K=1$ならば終了する．
2. 数字列$S$の隣り合った2つの数字$s_i,s_{i+1}$ ($1\le i \le K-1$)の和を$s'_i$とする．
3. $s'_i \ge10$の場合は10の位と1の位を足して置き換える． (例 $s'_i=13$の場合は $s'_i=1+3=4$と置き換える．)
4. $S=\{ s'_1,s'_2,\dots,s'_{K-1} \}$として置き換える．
5. 1の操作に戻る．

この操作で得られた1つの数字により運勢が分かるというものです．

例えば，数字列$S=\{ 3,5,8,2 \}$の場合について操作を行うと数字列Sは以下のように変化します．
$S=\{ 3,5,8,2 \}$
$S=\{ 8,4,1 \}$
$S=\{ 3,5 \}$
$S=\{ 8 \}$
この場合，最終的に得られる数字は8となります．

この占いを行うと考えましたが，手計算するのは無理だとすぐに分かりました．
そこで，数字列$S$が与えられるので占いの結果を求めてください．

ただし，数字列$S$は非常に長いため，パラメータ$(n,x,a,b,m)$をもとに以下の方法で生成されます．
$r_1=x$
$r_i = ((r_{i-1} \ \text{XOR} \ a) + b) \bmod{m} $ $( 2 \le i \le n) $
$S =\{ r_1\bmod{10} , r_2 \bmod{10} , \cdots, r_{n} \bmod{10} \}$
ここで，XORは排他的論理和を表す演算子である．

入力

T
$n_1 \ x_1 \ a_1 \ b_1 \ m_1$
$n_2 \ x_2 \ a_2 \ b_2 \ m_2$
$\vdots$
$n_T \ x_T \ a_T \ b_T \ m_T$

1行目にテストケースの数Tが与えられる．$1\le T \le 10^5$
各テストケースは1行からなり，5つのパラメータ$n_i \ x_i \ a_i \ b_i \ m_i$が与えられる．$1\le i \le T$
ここで，$n_i$は数字列$S_i$の長さを表し，残りのパラメータは数字列$S_i$の生成に使われる．

入力は次の制約を満たします．
$1 \le n_i \le 10^7, \sum_{i=1}^{T} n_i \le 10^7$
$0 \le x_i \le 10^9, 0 \le a_i \le 10^9, 0 \le b_i \le 10^9, 1 \le m_i \le 10^9$

出力

各テストケースごとに，数字列$S_i$の占い結果を1行で出力してください．

サンプル

1
4 3 1 23 39

8

10
1 0 0 0 10
1 1 0 0 10
1 2 0 0 10
1 3 0 0 10
1 4 0 0 10
1 5 0 0 10
1 6 0 0 10
1 7 0 0 10
1 8 0 0 10
1 9 0 0 10

0
1
2
3
4
5
6
7
8
9

10
2 0 0 9 10
2 1 0 7 10
2 2 0 5 10
2 3 0 3 10
2 4 0 1 10
2 5 0 9 10
2 6 0 7 10
2 7 0 5 10
2 8 0 3 10
2 9 0 1 10

9
9
9
9
9
9
9
9
9
9

10
10 261841953 671191155 663795355 305410838
10 862899986 184211912 62933042 787920138
10 753226285 21356280 298276938 21255922
10 958211219 805249349 595459506 854076698
10 410276862 213541814 550850232 377093341
10 357163853 623258597 838281966 723982380
10 614756466 807929090 709298917 299243176
10 523897658 967067335 799279896 655953200
10 626854805 479600382 724964117 820523234
10 287024904 121730613 972092257 520943977

1
3
3
9
7
8
9
2
1
9