For any integer i>=3 we have  F[i]=(F[i-1]+2*F[i-2]+3*F[i-3])%9901;

Now give you F[0],F[1],F[2],can you tell me the value of F

Fist Line, an integer Q(1<=Q<=100) represent the number of cases;

Every case is a line of four integers:F[0],F[1],F[2],n;

(0<=F[0],F[1],F[2]<9901,0<=n<100000000)

For each case ,you are request to output one integer the value of F[n] in one line.

4
1 2 3 3
4 5 6 5
2 3 4 2
4 5 6 100000

10
129
4
6086