Description

Time flies, and it is the NOI Qualifier season again...

This is student $Q$'s second time taking the provincial team selection contest. This year, after learning a hard lesson, student $Q$ no longer takes the risk of stealing problems, but instead improves personal skills by practicing old problems. However, there are too many old problems. Student $Q$ works on them day and night, yet still cannot see where the light ahead is.

One day, exhausted from doing too many problems, student $Q$ fell asleep and dreamed that, in the exam room, he encountered a problem that seemed familiar, but he could not remember how he had solved it before. Even after waking up, he was still frightened.

Student $Q$ frowned, feeling that something was wrong, so he came to you and hoped you could teach him how to solve this problem. Student $Q$ vaguely remembered that the task was to compute the value of the following expression:

$$(\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}d(ijk))\bmod (10^9+7)$$

Here, $d(ijk)$ denotes the number of divisors of $i \times j \times k$.

Input Format

The first line contains a positive integer $T$, meaning there are $T$ groups of testdata.

The next $T$ lines each describe one group of testdata, containing three integers $A, B,$ and $C$, with meanings as described above.

Output Format

For each group of testdata, output one line containing one integer, which is the value of the required expression.

5
10 10 10
100 100 100
1000 1000 1000
10000 10000 10000
100000 100000 100000

11536
51103588
165949340
19234764
176764584

Hint

For the testdata worth $30$ points, $1 \le A, B, C \le 5000$.

For the testdata worth $100$ points, $1 \le T \le 10$, $1 \le A, B, C \le 10^5$, and $1 \le \sum \max(A, B, C) \le 2 \times 10^5$.

Translated by ChatGPT 5