Problem Description

$\ \ \ \ $Holion August will eat every thing he has found.

$\ \ \ \ $Now there are many foods,but he does not want to eat all of them at once,so he find a sequence.

$f_n=\left\{\begin{matrix}
1 ,&n=1 \\
a^b,&n=2 \\
a^bf_{n-1}^cf_{n-2},&otherwise
\end{matrix}\right.$

$\ \ \ \ $He gives you 5 numbers n,a,b,c,p,and he will eat $f_n$ foods.But there are only p foods,so you should tell him $f_n$ mod p.

Input

$\ \ \ \ $The first line has a number,T,means testcase.

$\ \ \ \ $Each testcase has 5 numbers,including n,a,b,c,p in a line.

$\ \ \ \ 1\le T \le 10,1\le n\le 10^{18},1\le a,b,c\le 10^9$,$p$ is a prime number,and $p\le 10^9+7$.

Output

$\ \ \ \ $Output one number for each case,which is $f_n$ mod p.

1
5 3 3 3 233

190