function-3
Source: hackerearth
Difficulty: EASY

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) 

SAMPLE INPUT
1
3 3 3 4

SAMPLE OUTPUT
3