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 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
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:0.117s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Based on the problem FRACTION