Xiao C is an enthusiast of algorithmic competitions, and his specialty is handling sequence problems.

One day, Xiao C encountered a tricky sequence problem. Unlike typical sequences, this one is infinitely long! There is an infinitely long sequence $x_1, x_2, \cdots$ indexed starting from $1$. Performing one operation on the sequence transforms it such that the new sequence becomes $x_i + x_{i+1}$. At the same time, Xiao C observed that the sequence initially possesses a very elegant property: it repeats every $n$ numbers, i.e., $\forall i, x_i = x_{(i-1) \bmod n + 1}$.

Now, Xiao C needs to solve $q$ problems. At the beginning of each problem, the sequence is reset to $0$. Next, Xiao C assigns $1$ to all $x_t$ in the sequence where $t = m_i + c \cdot n_i$ for $c = 0, 1, 2, \cdots$. Then, Xiao C wants to know the value of $x_{pos_i}$ after performing $k_i$ operations on the sequence. Of course, the value of $x_{pos_i}$ after multiple operations might be very large, so you only need to output the value of $x_{pos_i}$ modulo $p_i$.

Input

The first line contains a single integer $q$.

Each of the following lines contains five integers $n_i, m_i, k_i, pos_i, p_i$.

Output

Output $q$ lines, each containing one integer, representing the answer to each query.

Examples

Input 1

10
4 3 2 3 9900101
5 5 5 1 9900091
6 5 1 4 9900091
40 38 14 6 9900161
46 14 31 9 9900857
49 15 33 12 9901627
390 175 377 238 9900931
335 240 466 328 9907291 
2653 1204 3563 891 9911609
3872 3142 4144 1787 9908449

Output 1

1
5
1
0
169911
5456
762581
7846051
5523436
2847830

Subtasks

• Subtask 1 (10 pts): $n_i \leq 2$
• Subtask 2 (20 pts): $n_i \leq 20$
• Subtask 3 (20 pts): All $n_i$ are distinct, $k_i \le 10^6$, $\forall i, j, p_i = p_j$.
• Subtask 4 (50 pts): No special restrictions.

For all data, $0 \leq q \leq 500$, $1 \leq m_i \leq n_i \leq 10^5$, $\sum n_i \leq 10^6$, $1 \leq k_i \leq 10^9$, $1 \leq pos_i \leq n$, $p_i$ is a prime number such that $p_i \leq 10^7$, and $n_i \mid (p_i - 1)$.