Note

Problem Statement

Everyone, have you heard of fortune telling using digits?
For a digit sequence $S=\{ s_1,s_2,\dots,s_N \}$ consisting of the digits 0-9, perform the following operations.

1. Let $K$ be the length of the digit sequence $S$. If $K=1$, terminate.
2. Let $s'_i$ be the sum of two adjacent digits $s_i,s_{i+1}$ ($1\le i \le K-1$).
3. If $s'_i \ge10$, replace it with the sum of its tens digit and its ones digit. (For example, if $s'_i=13$, replace it with $s'_i=1+3=4$.)
4. Replace $S$ with $S=\{ s'_1,s'_2,\dots,s'_{K-1} \}$.
5. Return to operation 1.

The single digit obtained by these operations tells you your fortune.

For example, when the operations are performed on the digit sequence $S=\{ 3,5,8,2 \}$, the digit sequence S changes as follows.
$S=\{ 3,5,8,2 \}$
$S=\{ 8,4,1 \}$
$S=\{ 3,5 \}$
$S=\{ 8 \}$
In this case, the digit finally obtained is 8.

I thought about doing this fortune telling, but I soon realized that calculating it by hand was impossible.
So, given the digit sequence $S$, find the result of the fortune telling.

However, since the digit sequence $S$ is very long, it is generated from the parameters $(n,x,a,b,m)$ in the following way.
$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} \}$
Here, XOR is the operator denoting exclusive OR.

Input

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$

The first line gives the number of test cases T. $1\le T \le 10^5$
Each test case consists of one line, which gives the five parameters $n_i \ x_i \ a_i \ b_i \ m_i$. $1\le i \le T$
Here, $n_i$ denotes the length of the digit sequence $S_i$, and the remaining parameters are used to generate the digit sequence $S_i$.

The input satisfies the following constraints.
$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$

Output

For each test case, output the fortune telling result for the digit sequence $S_i$ on one line.

Sample

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