408809: GYM103328 F Prime Gifts

It's Christmas time! There are $$$p$$$ children in the Prime Town, and of course, in Prime Town, $$$p$$$ is a prime number. Santa Claus would like to give each child the same amount of presents. There are two types of gifts available: gift A and gift B. However, Santa Claus cannot buy gift A or gift B arbitrarily. Instead, the only available option is to buy a combo containing $$$x$$$ gifts A and $$$y$$$ gifts B, where $$$x, y \geq p$$$

He wants to make every child equally happy, so he decides to distribute the gifts he buys to the children such that each child gets the same number of gift A and the same number of gift B.

There are only $$$p - 1$$$ combos left in stock. Santa Claus is rich, and as a result, he cares more about the number of wasted gifts than the money he spends on buying them. Therefore, he wants to choose the optimal number of combos to buy, so that after distributing them to the children evenly, the number of remaining gifts is minimized. Of course, he can simply buy nothing, and there will be no waste. However, that would make him an unethical Santa Claus, and thus it's forbidden to do so.

He wonders, what is the minimum number of remaining gifts if he buys the optimal number of gift combos?

Of course, Santa Claus knows some basics of competitive programming, and this problem should have been an easy task for him. Still, you should mind that he is Santa Clauses in $$$T$$$ different parallel universes, having their own $$$x, y, p$$$, respectively.

He has to solve it before Christmas, and there is no time to waste. Desperately, he adds this problem into the problem set so that some contestants might incidentally solve it during the contest.

The first line of the input contains a single integer $$$T$$$ — the number of test cases. Each of the next $$$T$$$ lines contains three integers $$$p$$$, $$$x$$$, and $$$y$$$ separated by spaces.

• $$$1 \leq T \leq 10^5$$$
• $$$2 \leq p \leq 10^9$$$
• $$$p \leq x, y \leq 10^{18}$$$
• It's guaranteed that $$$p$$$ is a prime number

For each of the $$$T$$$ test cases, output a line containing the answer to that test case.

2
3 4 7
7 16 10

2
4

For the first sample case, you can buy 1 combo and give each child 1 gift A and 2 gifts B.

For the second sample case, you can buy 5 combos and give each child 11 gifts A and 7 gifts B.