Description:

Fib数大伙儿都应该很熟悉了吧。可现在却有个山寨Fib数，其定义是：
F(n)=a n=1
F(n)=b n=2
F(n)=F(n-1)+F(n-2) n>2 is odd
F(n)=F(n-1)+F(n-2)+F(n-3) n>2 is even
这里a和b预先给出。
给你a,b,n，你的任务是计算F(n)。

Input:

第一行给出一个整数T，描述后面将会出现T组数据。每组数据包含a,b,n(0≤a,b≤10，0<n≤30)。

Output:

对于每组数据，在一行中，输出对应的F(n)值。

Sample Input:

2
1 2 3
1 3 6

Sample Output:

3
24