Linear Programming?

fsshakkhor Father Timm Memorial Prog...
Limits 1s, 512 MB

Given the value aa, bb and NN. Find the number of non-negative integer pairs (x1,x2)(x_1,x_2) which satisfies the following inequality.

a×x1+b×x2Na \times x_1 + b \times x_2 \leq N

Input

First line contains an integer T (1T104)T~(1 \leq T \leq 10^4) denoting the number of test cases.

Each test case contains three integers NN, aa and bb.


Subtask 11 (10 Points): 1N1041 \leq N \leq 10^4, 2a10002 \leq a \leq 1000

Subtask 22 (30 Points): 1N1091 \leq N \leq 10^9, a=2a=2

Subtask 33 (60 Points): 1N1091 \leq N \leq 10^9, 2a10002 \leq a \leq 1000

For all subtasks 1bN1 \leq b \leq N.

Output

For each test print the answer in a single line.

Sample

InputOutput
2
5 2 3
10 4 1
5
21

The first inequality is 2x1+3x252 x_1 + 3 x_2 \leq 5.

The following 55 pairs of (x1,x2)(x_1,x_2) satisfies it.

(0,0),(0,1),(1,0),(1,1),(2,0)(0,0), (0,1),(1,0),(1,1),(2,0).


Submit

Login to submit.

Statistics

43% Solution Ratio
Nahian9696Earliest, 3w ago
Nahian9696Fastest, 0.0s
Desh01Lightest, 5.7 MB
ShimantoShortest, 581B
Toph uses cookies. By continuing you agree to our Cookie Policy.