Time flies, and in the blink of an eye, another year has passed...

This is the second time student Xiao Q is participating in the provincial team selection contest. This year, Xiao Q has learned his lesson; instead of risking stealing the exam questions, he is improving his skills by practicing old exam questions. However, there are too many old questions, and although Xiao Q works on them day and night, he cannot see the light at the end of the tunnel.

One day, exhausted from overworking, Xiao Q fell asleep and dreamed that he encountered a problem in the exam hall that he felt he had solved before, but he could not remember how he had solved it. He still felt a lingering fear even after waking up.

Xiao Q frowned, sensing that something was wrong, so he came to you, hoping you could teach him how to solve this problem. Xiao Q vaguely remembers that the problem asks to calculate the value of the following expression:

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

where $d(ijk)$ denotes the number of divisors of $ijk$.

Input

The first line contains a positive integer $T$, representing the number of test cases.

The next $T$ lines each describe a test case, containing three integers $A, B,$ and $C$, with meanings as described in the problem statement.

Output

For each test case, output a single line containing an integer representing the value of the requested expression.

Examples

Input 1

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

Output 1

11536
51103588
165949340
19234764
176764584

Notes

For 30% of the data, $1 \le A, B, C \le 5000$.

For 100% of the data, $1 \le T \le 10, 1 \le A, B, C \le 10^5, 1 \le \sum \max(A, B, C) \le 2 \cdot 10^5$.