Description

这年头，什么东西都玩山寨，我们也来凑个热闹吧。菲波那契数列你当然是熟悉的，那么看一个“山寨”菲波那契数列吧，它的递推式如下： 式中a和b是常数。给定a、b和n，计算对应的F(n) 的值。 

Input

第一行输入测试用例的个数T；后面T行分别输入测试的用例，每个测试一行，内容分别为整数a、b和n。已知数据范围：a<=10,b<=10,n<=30。

Output

输出对应的F(n)的值，每个样例结果占据一行。

Sample Input

2
1 2 3
1 3 6

Sample Output

3
24

HINT

Source

The 9th NBU Programming Contest