1323 : A Simple Problem

Haze is weak in English, so he would like to description this problem as simple as possible. He want you to calculate a formula that is F(a,b,k,p).
$ F(a,b,k,p)=a^{b^{b^{b\cdots (k\, times)}}}\% p $

The first line consist a number T presented the number of test case. Each of following T lines has four figures, a,b,k,p.
Limits:
$1 \leq T \leq 1000, 1 \leq  a,b,p \leq 10^7, 1 \leq k \leq 10^{18}$

Print T lines, and every line has the result for the four parameters. 

3
2 3 1 10000
3 2 2 80
342 234 567 89

8
1
2

第二届湖北省赛