Linear Programming?

Limits 1s, 512 MB

Given the value $a$ , $b$ and $N$ . Find the number of non-negative integer pairs $(x_1,x_2)$ which satisfies the following inequality.

a \times x_1 + b \times x_2 \leq N

Input

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

Each test case contains three integers $N$ , $a$ and $b$ .

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

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

Subtask $3$ (60 Points): $1 \leq N \leq 10^9$ , $2 \leq a \leq 1000$

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

For each test print the answer in a single line.

Input	Output
2 5 2 3 10 4 1	5 21
The first inequality is $2 x_1 + 3 x_2 \leq 5$ . The following $5$ pairs of $(x_1,x_2)$ satisfies it. $(0,0), (0,1),(1,0),(1,1),(2,0)$ .

Input

Output

2
5 2 3
10 4 1

5
21

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

The following $5$ pairs of $(x_1,x_2)$ satisfies it.

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