Problem Description

Given A, B, C, Calculate

Where φ(n) denotes the number of positive integers ≤ n that are relatively prime to n.

Input

The first line of the input contains an integer T , denoting the number of test cases. In each test case, there are three integers A, B, C in one line, as described above.
1 ≤ T ≤ 10, 0 < A, B, C ≤ 10^7

Output

For each test case, output one line contains a single integer, denoting the answer modulo 2^30.

4
96 93 95
970 906 893
92460 95043 54245
9760979 8053227 7156842

1114536
28070648
388873924
623507672