Kodi has been bought at the auction in the NIT Premier League. Kodi is a batsman and the runs he makes in each innings depends on the runs he has made in his previous three innings. The runs he makes in the current innings is given by the formula :
F(x) = ( 2xF(x-1)-(x-1)F(x-2)-(x-2)*F(x-3) )/3
where F(i) = runs Kodi makes in ith innings
The number of innings Kodi plays can be infinite.
When x is given , find F(x)
Input
first line contains T . no of test cases
next t lines contains F(0),F(1),F(2) and x .
Output
F(x)
Constraint
0 < T < 100
0 <= x <= 1000000
0 <= F(i) <= 100000
F(0)=F(1)=F(2)