Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Vietnamese] as well.

Ben Fero is a popular guy who likes inventing and solving interesting problems. Last weekend, he found a challenging problem, but he could not solve it on his own, so he decided to ask you for help. Can you help Ben Fero solve this problem?

You are given three integers $A$, $B$ and $C$. Let's call a triple of integers $(a, b, c)$ interesting if it satisfies the following criteria:
$1 ≤ a ≤ A$, $1 ≤ b ≤ B$ and $1 ≤ c ≤ C$
for any two real numbers $x$ and $y$ such that $x \neq 0$ and $y \neq 0$, $ax^{2} + 2bxy + cy^{2} > x^{2} + y^{2}$ holds

You should find the number of interesting triples. Since this number could be very large, compute it modulo $10^{9}+7$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $A$, $B$ and $C$.

------ Output ------
For each test case, print a single line containing one integer ― the number of interesting triples modulo $10^{9}+7$.

------ Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ A, C ≤ 10^{9}$
$1 ≤ B ≤ 5,000$

------ Subtasks ------
Subtask #1 (30 points): $1 ≤ A, B, C ≤ 100$

Subtask #2 (20 points): $1 ≤ A, B, C ≤ 5,000$

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------
2
2 5 3
3 2 4
----- Sample Output 1 ------
1
6
----- explanation 1 ------
Example case 1: There is only one interesting triple: $(2, 1, 3)$.

Example case 2: The interesting triples are $(2, 1, 3)$, $(2, 1, 4)$, $(3, 1, 2)$, $(3, 1, 3)$, $(3, 1, 4)$ and $(3, 2, 4)$.

见题面

见题面