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
hide comments
[Rampage] Blue.Mary:
20161007 12:50:09
The last (constant) optimization is a little boring.


:D:
20161006 10:25:22
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: 20161006 10:26:51 

[Rampage] Blue.Mary:
20161006 02:04:55
RE :D: The O(sqrt(N)) complexity of my algorithm is NOT depending on the factorization part. 

:D:
20161005 23:34:39
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.


Min_25:
20160308 17:30:41
@Blue.Mary


[Rampage] Blue.Mary:
20160308 16:46:31
Are test cases (almost) randomly generated? Or contains (large numbers of) manually constructed ones?

Added by:  Min_25 
Date:  20160308 
Time limit:  3s6s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  PAIRDIV 