피보나치 수열 fn 은 다음과 같은 점화식을 만족하는 수열이다.

이 때 의 값을 구하는 것은 매우 간단한 일이다. 그러므로 f1 과 f2 의 값이 다른 값으로 주어질 때의 의 값을 구해보자.

입력

• 첫 번째 줄에 테스트 케이스의 개수 T가 입력된다.
• 그 다음 T줄에는 각 줄마다 각 테스트 케이스가 주어진다. 각 줄은 3개의 정수로 이루어져 있으며, 순서대로 f1 ,f2 , N 을 나타낸다.

출력

입출력 예

입력 

2 
1 1 5 
2 5 4 

출력 

40 
222 

힌트

출처:august14