P19481 [HackerEarth] 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
普及-
题目描述

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

输入格式

见题面

输出格式

见题面

样例输入
100 89384 89384 89384 6930887 92778 92778 92778 4636916 47794 47794 47794 4238336 85387 85387 85387 9760493 16650 16650 16650 9641422 2363 2363 2363 490028 68691 68691 68691 2520060 97764 97764 97764 7513927 80541 80541 80541 383427 89173 89173 89173 3455737 5212 5212 5212 1595369 2568 2568 2568 6956430 65783 65783 65783 1021531 22863 22863 22863 3665124 74068 74068 74068 8703136 13930 13930 13930 1979803 34023 34023 34023 5723059 33070 33070 33070 5898168 61394 61394 61394 9018457 75012 75012 75012 6478043 76230 76230 76230 3377374 84422 84422 84422 4544920 13785 13785 13785 6898538 75199 75199 75199 3594325 98316 98316 98316 8664371 66414 66414 66414 4803527 76092 76092 76092 4268981 59957 59957 59957 9241874 6863 6863 6863 2999171 6997 6997 6997 5497282 2306 2306 2306 4420926 77085 77085 77085 7336328 60337 60337 60337 9126506 50847 50847 50847 2621730 61314 61314 61314 3925858 16125 16125 16125 4353896 19583 19583 19583 1100546 98815 98815 98815 8233368 15435 15435 15435 5990365 44044 44044 44044 313751 71088 71088 71088 6426809 17277 17277 17277 9947179 95789 95789 95789 9393585 5404 5404 5404 8502652 92755 92755 92755 4612400 99933 99933 99933 4095061 49677 49677 49677 3993369 47740 47740 47740 4210013 36227 36227 36227 9698587 48095 48095 48095 6297540 40796 40796 40796 3480571 51435 51435 51435 5960379 97468 97468 97468 2066602 10098 10098 10098 7612903 73318 73318 73318 3570493 26653 26653 26653 260757 97302 97302 97302 5560281 24287 24287 24287 3209442 53866 53866 53866 4429690 28445 28445 28445 7346620 58441 58441 58441 744730 58032 58032 58032 3108118 38098 38098 38098 7905772 34482 34482 34482 2890676 20710 20710 20710 1698928 4568 4568 4568 8777857 79498 79498 79498 4872354 54587 54587 54587 2276966 55307 55307 55307 3964684 6220 6220 6220 28625 51529 51529 51529 332872 5733 5733 5733 48830 9504 9504 9504 5530020 58271 58271 58271 3363369 59709 59709 59709 7486716 26341 26341 26341 1518150 47797 47797 47797 9700724 42619 42619 42619 8002246 22847 22847 22847 9493452 92922 92922 92922 243556 92380 92380 92380 2597489 37765 37765 37765 8888229 69842 69842 69842 8792351 65194 65194 65194 9441501 57035 57035 57035 6087765 70125 70125 70125 5324915 36988 36988 36988 2275857 73744 73744 73744 7346492 22228 22228 22228 1148366 9860 9860 9860 281937 51433 51433 51433 6452552 16438 16438 16438 1899229 53276 53276 53276 3975408 1475 1475 1475 6276122 68859 68859 68859 794396 36030 36030 36030 4661238 8236 8236 8236 573794 65819 65819 65819 5894429 66144 66144 66144 7231012 35929 35929 35929 4639530
样例输出
89384 92778 47794 85387 16650 2363 68691 97764 80541 89173 5212 2568 65783 22863 74068 13930 34023 33070 61394 75012 76230 84422 13785 75199 98316 66414 76092 59957 6863 6997 2306 77085 60337 50847 61314 16125 19583 98815 15435 44044 71088 17277 95789 5404 92755 99933 49677 47740 36227 48095 40796 51435 97468 10098 73318 26653 97302 24287 53866 28445 58441 58032 38098 34482 20710 4568 79498 54587 55307 6220 51529 5733 9504 58271 59709 26341 47797 42619 22847 92922 92380 37765 69842 65194 57035 70125 36988 73744 22228 9860 51433 16438 53276 1475 68859 36030 8236 65819 66144 35929