E :: GCD

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Suppose that f(i,j,k) is defined to be the greatest common divisor of i,i+j,i+2j,…,i+(k-1)j,i+kj. Write a program that gets n, m and p as the input and computes the following as the output.

http://sharecode.ir/assets/problem_images/2732_81c11cdde38dea7a74e1af5cefd2df2a.jpg

Input

The first line of the input includes the number of test cases, 1≤t≤100. Each of the following t lines contains three positive integers n, m and p separated by a single space.  All input numbers are not greater than 1200.

Output

For each test case, print the output of your program in one line.

Sample Input

2
2 3 4 
4 5 6

Sample Output

28
168
Submit

Source: 12th Iran Nationwide Internet Contest I