One of the most fundamental concepts learnt by a novice programmer is generation of Fibonacci Series. The Fibonacci Series is known to be of the form 0 1 1 2 3 5 8 13... etc. Usually a recursive approach to solve the problems is applied. The problem with the usual recursive approach is that multiple calls are made to calculate the same number, which makes it time in-efficient. This algorithm runs in time theta(n). However, if you use either a Dynamic Programming approach or Memoization Technique, we can develop an algorithm that computes the nth Fibonacci number using at most O(log n) arithmetic operations.
Your task is to write a program, using Dynamic Programming or Memoization or otherwise that computes the nth Fibonacci Number in O(log n). The series need not begin from 0 1.
Problem Setter:

Input
The input will contain the number of test cases 'T' an integer. The next 'T' line contain 3 unsigned integers A, B and N (in each line) where A and B are respectively the first and the second term of the Modified Fibonacci series and N is the Nth term to be calculated.
Limits are as follows - 0 < A, B, T

Output
You have to print the Nth Fibonacci term for each test case in the new line.

Example

Input:
7
0 1 10
2 3 5
67 101 9
23 46 35
45 37 24
45 27 1
45 46 2

Output:
34
13
2992
343398096
1857304
45
46

见题面

见题面