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

Output

3
24