P3312 [SDOI2014] Number Table

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$.

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.

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

### 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