피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21, ... 과 같이 앞에 있는 두 수를 더하여 계속 이어 가는 수열이다.

A, B, A+B, B+(A+B), (A+B)+(B+A+B)... 와 같은 피보나치 수열에서 N번째에는 무슨 수가 있을까?

입력

1번째 줄에는 데이터의 개수 M이 주어진다.(1≤M≤1,000,000)

2~M+1번째 줄에는 A, B, N이 공백으로 구분되어 주어진다. (1≤A,B,N≤35)

출력

1~M번째 줄에 N번째에 있는 수를 차례대로 출력한다.

입출력 예

입력

4
1 1 5
1 1 6
1 2 6
3 6 9

출력

5
8
13
165 

출제:tncks0121