It is holi festival, festival of colors. Devu is having fun playing holi and is throwing balloons with his girlfriend Glynis. Police saw this mischief and tried arresting his girlfriend, Devu being a mathematician asked police not to arrest his girlfriend and instead torture him with brain teaser. Devu was a young engineering fellow and he did not knew that policeman was equally good in mathematics, policeman gave Devu a problem which is as follows:

Let $f(n,k)=n^k$

Your aim is to answer $f(n_1,k_1)^{f(n_2,k_2)}\:\text{mod}\:n$

Can you help devu and his girlfriend rescue from modern police.

Input Format

You are given ${T}$ which is the number of queries to solve.

Each Query consist of 5 space separated integers $n_{1},k_{1},n_{2},k_{2},n$

Constraints

$1\leq T\leq10^4$
$0\leq n_1,k_1,n_2,k_2\leq10^9$
$1\leq n\leq10^7$

Note The output to ${{0}^{{0}$ should be ${1}$.

Output Format

Output contains exactly ${T}$ lines. $i^{\cdot th}$ line containing the answer for the $i^{\cdot th}$ query.

Sample Input
1
2 1 2 2 15

Sample Output
1

Explanation

$f(2,1)=2$

$f(2,2)=4$

so answer is $16\:\text{mod}\:15=1$

见题面

见题面