FNRANK  Rank of a Fraction
Let us consider a set of fractions x/y, such that 0 <= x/y <= 1, y <= n and gcd (x, y) = 1.
For example, say n = 5. Then we have the following set in increasing order :
^{0}⁄_{1}, ^{1}⁄_{5}, ^{1}⁄_{4}, ^{1}⁄_{3}, ^{2}⁄_{5}, ^{1}⁄_{2}, ^{3}⁄_{5}, ^{2}⁄_{3}, ^{3}⁄_{4}, ^{4}⁄_{5}, ^{1}⁄_{1}
You are given n, a and b. The task is to find the rank of a/b in a set of fractions as stated above which is in increasing order.
Input
The first line of the input contains t (t <= 20), the number of testcases. Then t lines follow. In each of the t lines you are given n, a and b. (n <= 100000)
Output
Print t lines. The ith line contains the rank of a fraction a/b for a given n, a and b in the (i + 1)th line of input. All answers fit within a signed integer.
Example
Input:
2
5 3 4
8 5 7
Output:
9
17
hide comments
hackerbhaiya:
20200803 20:58:53
Use of inclusion and exclusion property!! 

black_shroud:
20200615 13:58:27
use long long costed 10WA


Farhan Hasin:
20190902 04:40:32
Let's get to all X from 1 to N and check how many Y/X are there who are less than A/B and gcd(X, Y)=1. To do this,


parijat bhatt:
20150131 18:38:04
am using the the formula to generate its next numbers but still tle:( 
Added by:  Paranoid Android 
Date:  20100307 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Based on the problem FRACTION 