小C是一个算法竞赛爱好者，他最擅长处理的就是序列问题。

有一天小 C 遇到了一个棘手的序列问题，与一般的序列不同，这个序列有无限长！现在有一个下标从 $1$ 开始的无限长的序列 $x_1, x_2, \cdots$。对该序列进行一次操作，会使得操作后的序列 $=x_i + x_{i+1}$。同时小 C 观察到这个序列一开始有一个非常优美的性质：每隔 $n$ 个数开始循环,即 $\forall i, x_i = x_{(i-1) \bmod n + 1}$。

现在小 C 需要解决 $q$ 个问题，每个问题开始时，序列会重置为 $0$。接下来，小 C 会将这个序列中所有 $x_t$ 都赋为 $1$，其中 $t=m_i + cn_i, c=0,1,2,\cdots$ 然后小 C 想知道，对这个序列操作 $k_i$ 次后，$x_{pos_i}$ 的值是多少？当然，多次操作后与 $x_{pos_i}$ 的值可能过大，你只需要输出 $x_{pos_i}$ 在模$p_i$ 意义下的取值即可。

输入格式

第一行，包含一个数 $q$。

接下来一行，每行五个数 $n_i, m_i, k_i, pos_i, p_i$。

输出格式

输出 $q$ 行，每行一个数，表示每个询问的答案。

样例数据

样例输入

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

样例输出

1
5
1
0
169911
5456
762581
7846051
5523436
2847830

子任务

• Subtask 1(10 pts): $n_i \leq 2$
• Subtask 2(20 pts): $n_i \leq 20$
• Subtask 3(20 pts): $n_i$ 互不相同，$k_i \le 10^6$，$\forall i, j, p_i = p_j$。
• Subtask 4(50 pts): 无特殊限制。

对于所有数据，$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$ 为质数且 $p_i \leq 10^7$，$n_i \mid (p_i - 1)$。