## 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 :

01, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11

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 test cases. 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
 David: 2022-02-23 22:14:55 First Java solution! hackerbhaiya: 2020-08-03 20:58:53 Use of inclusion and exclusion property!! black_shroud: 2020-06-15 13:58:27 use long long costed 10WA Farhan Hasin: 2019-09-02 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, first of all, Y/X < A/B, so Y<(A*X)/B. So all we have to do is to find the count of Y so that Y<(A*X)/B and gcd(X, Y)=1 for all X. We can do that with the Mobius function. Last edit: 2019-09-02 04:41:40 parijat bhatt: 2015-01-31 18:38:04 am using the the formula to generate its next numbers but still tle:(

 Added by: Paranoid Android Date: 2010-03-07 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: Based on the problem FRACTION