You are given a sequence whose term is

Input Format

The first line of input contains , the number of test cases.
Each test case consists of three lines, each containing , and respectively.

Output Format

For each test case, print the required answer in a line.

Constraints

Sample Input

2
2
5
2
3
4
3

Sample Output

1146
5988

Explanation

Case 1:
Case 2: