Description

There is an $n\times m$ table of numbers. The value at row $i$ and column $j$ ($1\le i\le n$, $1\le j\le m$) equals the sum of all natural numbers that divide both $i$ and $j$. Given $a$, compute the sum of all numbers in the table that are not greater than $a$.

Input Format

The input contains multiple test cases.

The first line contains an integer $Q$, the number of test cases.

Each of the next $Q$ lines contains three integers $n$, $m$, $a$ ($|a|\le 10^9$), describing one test case.

Output Format

For each test case, output one line with a single integer: the answer modulo $2^{31}$.

2
4 4 3
10 10 5

20
148

Hint

Constraints and Conventions

For all testdata, $1\le n,m\le 10^5$, $1\le Q\le 2\times 10^4$.

Translated by ChatGPT 5