本题没有可用的提交语言。

<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css" integrity="sha384-wITovz90syo1dJWVh32uuETPVEtGigN07tkttEqPv+uR2SE/mbQcG7ATL28aI9H0" crossorigin="anonymous">

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