There is an $n \times m$ table where the value at the $i$-th row and $j$-th column ($1 \le i \le n, 1 \le j \le m$) is the sum of all natural numbers that divide both $i$ and $j$. Given $a$, calculate the sum of all numbers in the table that are no greater than $a$.
Input
The input contains multiple test cases.
The first line contains an integer $Q$, representing the number of test cases. Each of the following $Q$ lines contains three integers $n, m, a$ ($|a| \le 10^9$) describing a test case.
Output
For each test case, output a single integer representing the answer modulo $2^{31}$.
Constraints
| Test Case | $n, m$ | $Q$ |
|---|---|---|
| 1~3 | $1 \le n, m \le 400$ | $1 \le Q \le 200$ |
| 4~6 | $1 \le n, m \le 10^5$ | $1 \le Q \le 10$ |
| 7~10 | $1 \le n, m \le 10^5$ | $1 \le Q \le 2 \times 10^4$ |
Examples
Input 1
2 4 4 3 10 10 5
Output 1
20 148