PAIRDIV2 - Pair Divisible 2

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

Added by:Min_25
Date:2016-03-08
Time limit:3s-6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:PAIRDIV

hide comments
2016-10-07 12:50:09 [Rampage] Blue.Mary
The last (constant) optimization is a little boring.

(Re: Min_25)
I'm sorry about that. I should have decreased the number of testcases a little..

Last edit: 2016-10-08 04:27:44
2016-10-06 10:25:22 :D
Ok, sorry. I was looking through the perception of my approach and though O(sqrt(N)) is the complexity of factorization and a bottle neck for the entire program (if not for prime factor limit).

Last edit: 2016-10-06 10:26:51
2016-10-06 02:04:55 [Rampage] Blue.Mary
RE :D: The O(sqrt(N)) complexity of my algorithm is NOT depending on the factorization part.
2016-10-05 23:34:39 :D
I don't understand the issue. Factorization is not a problem here. Limit on prime factors takes care of that. I actually used very naive factorization function in an AC solution.

Thanks for this version Min_25. It really got me thinking.

(Re: Min_25)
Thank you. I appreciate it. :)

Last edit: 2016-10-07 17:04:31
2016-03-08 17:30:41 Min_25
@Blue.Mary
Most of the test cases are manually constructed.

The desired (C++) solution runs for 0.010 second per test case (in the worst case).

Last edit: 2016-03-12 00:57:30
2016-03-08 16:46:31 [Rampage] Blue.Mary
Are test cases (almost) randomly generated? Or contains (large numbers of) manually constructed ones?

Also, I wonder the required time factor for this problem. My program now runs for 0.6 second per test case (in the worst case). Is it far from the desired solution?

Last edit: 2016-03-08 17:00:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.