The kindergarten is preparing for the new year, and the teacher !A !B !C decided to organize the children to prepare decorations and send them to Santa Claus to decorate his reindeer.
The children took the idea with interest and cut out $$$a$$$ stars and $$$b$$$ snowflakes from paper. Now they plan to mail them to Santa Claus. They loved the decorations they cut so much that they might decide to keep a part for themselves. Thus, children can send Santa $$$x$$$ stars and $$$y$$$ snowflakes, where $$$0 \le x \le a$$$ and $$$0 \le y \le b$$$. So that Santa doesn't get upset, children should send him at least one decoration. That is, the condition $$$x + y \gt 0$$$ must also be satisfied.
For all reindeer to look beautiful, each must have the same number of decorations. It is known that Santa has $$$n$$$ reindeer, so if $$$x$$$ stars and $$$y$$$ snowflakes are sent, $$$x+y$$$ must be divisible by $$$n$$$.
The teacher was interested: how many different ways there are to compose a package to Santa Claus. Two ways are considered different if they differ in the number of stars or the number of snowflakes.
One test case contains multiple tests. Each test must be solved independently.
The first line of the input contains an integer $$$t$$$ — the number of tests ($$$1 \le t \le 10^5$$$).
The following lines describe the tests, one per line. The test description consists of three integers $$$n$$$, $$$a$$$ and $$$b$$$ — the number of reindeer Santa has, the number of stars and the number of snowflakes carved by children ($$$4 \le n \le 10^9$$$; $$$0 \le a, b \le 10^9$$$).
Print $$$t$$$ numbers. For each test case, print one number: the number of ways to compose a package for Santa Claus.
Points for each subtask are awarded only if all tests for this subtasks and required subtasks have been completed successfully.
| Subtask | Points | Additional restrictions | Necessary subtasks | Information about run | |
| 1 | 10 | $$$t = 1$$$, $$$a, b \le 1000$$$ | first fault | ||
| 2 | 10 | $$$t \le 1000$$$, $$$a = 0$$$ | first fault | ||
| 3 | 15 | $$$t \le 1000$$$, $$$a, b | lt; n \le 1000$$$ | first fault | |
| 4 | 10 | $$$t \le 1000$$$, $$$a, b \le 1000$$$ | 1, 3 | first fault | |
| 5 | 15 | $$$t = 1$$$, $$$n \le 1000$$$ | first fault | ||
| 6 | 10 | $$$t \le 1000$$$, $$$n \le 1000$$$ | 3, 5 | first fault | |
| 7 | 30 | — | 1 – 6 | first fault |
4 4 2 2 4 4 4 6 5 5 8 13 17
1 6 5 30
In the first test, Santa has $$$4$$$ reindeer, and the children cut $$$2$$$ stars and $$$2$$$ snowflakes. Only one set fits here — all cut out decorations need to be sent.
In the second test, Santa also has $$$4$$$ reindeer, but the children cut $$$4$$$ stars and $$$4$$$ snowflakes. 6 sets are suitable here: 0 stars and 4 snowflakes, 1 star and 3 snowflakes, 2 stars and 2 snowflakes, 3 stars and 1 snowflake, 4 stars and 0 snowflakes, 4 stars and 4 snowflakes.
