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

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 |