Let $C(N, a, b)$ be the number of integer pairs $(x, y)$ in $1 \le x \le a$, $1 \le y \le b$ such that $xy$ is divisible by $N$.

Given $N$, $a$ and $b$, find $C(N, a, b)$ modulo $10^{9}$.

Input

The first line contains $T$, the number of test cases.

In each of the next $T$ lines, you are given three numbers $N$, $a$ and $b$.

Output

For each test case, print $C(N, a, b)$ modulo $10^{9}$.

Constraints

$1 \le T \le 100$

$1 \le N \le 10^{18}$, $1 \le a \le 10^{18}$, $1 \le b \le 10^{18}$.

You can assume that the maximum prime factor of $N$ is less than or equal to $10^{5}$.

Example

Input

5
1 1 1
2 2 2
10 10 10
100 100 100
1 10000 100000

Output

1
3
27
520
0