How many points (x, y) with non-negative integer coordinates satisfy y ≤ ax / b and x ≤ n?

Input

The first line contains an integer T (T ≤ 100000). T lines follow, each contains three positive integers n, a, b, where n, a, b ≤ 10⁹ and a ≤ b.

Output

T lines, each contains a single integer denoting to the number of points according to the description.

Example

Input:
5
8 2 10
8 4 4
7 1 5
713241932 127894722 957823358
759096725 496666160 980149020

Output:
13
45
11
33963383064794976
145994569610845896

Warning: enormous input/output data, be careful with certain languages