The value of F[n]

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 161

Solved: 72

Description


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


Input


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)

Output


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


sample input
4
1 2 3 3
4 5 6 5
2 3 4 2
4 5 6 100000
sample output
10
129
4
6086
hint
source
Dongxu LI
© 2015 HUST ACMICPC TEAM. All Right Reserved.