SPOJ.com - Problem PAIRDIV2

PAIRDIV2 - Pair Divisible 2

#math #fast-moebius-transform

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

Submit solution!

hide comments



	[Rampage] Blue.Mary: 2016-10-07 12:50:09 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
	:D: 2016-10-06 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: 2016-10-06 10:26:51
	[Rampage] Blue.Mary: 2016-10-06 02:04:55 RE :D: The O(sqrt(N)) complexity of my algorithm is NOT depending on the factorization part.
	:D: 2016-10-05 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. 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
	Min_25: 2016-03-08 17:30:41 @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
	[Rampage] Blue.Mary: 2016-03-08 16:46:31 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

Submit solution!

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