F. Iura's Valentine
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For Valentine's Day, Iura was looking forward to getting some chocolates. Unfortunately, all he got was the gcd function, where $$$\gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Given $$$a$$$, $$$b$$$, $$$d$$$, help Iura find $$$$$$\sum_{i = 0}^{d} \gcd(a + i, b + i)$$$$$$ Since the answer could be large, find it modulo $$$10^9 + 7$$$.

Input

The first line will contain $$$T$$$, $$$1 \le T \le 10$$$, the number of testcases.

Each testcase will have three space separated integers $$$a$$$, $$$b$$$, and $$$d$$$, $$$1 \le a, b \le 10^9$$$, $$$1 \le d \le 10^{18}$$$.

Output

Print a single integer per testcase representing the sum.

Example
Input
2
1 7 5
2 8 8
Output
15
22