Problem Background

A magical story of commerce...

(Friendly reminder: Pay attention to the time limit!)

Problem Description

LiM owns a handmade pastry shop, which has accumulated $P$ regular customers (where $P$ is a prime number) due to its affordable and delicious pastries.

Every time the shop introduces a New Product, it makes many of them, and these $P$ customers all support the new product by:

Buying the same quantity from each person, and the total quantity should be as large as possible.

The shop has $B$ workers, who can produce $A$ times the quantity already produced in one minute.

(Note: Initially, there is one already-made New Product used as a sample for production.)

After production is complete and the purchase (considering only regular customers) is finished:

To consider the workers, there should be exactly $B$ left at the end.

Given the known conditions, please help LiM calculate the minimum amount of time needed to work!

Input Format

There are $T+1$ lines in total.

The first line contains a number $T$, indicating that there are $T$ New Products to be introduced.

Lines $2$ to $T+1$ each contain three numbers $P$, $A$, and $B$, with meanings as described in the problem.

Output Format

For each New Product:

If it is possible to achieve (it might not be possible), output the minimum number of minutes worked.

If it is not possible, output Couldn't Produce!.

Sample Input and Output

Sample Input #1

1
5 2 3

Sample Output #1

3

Sample Input #2

1
2 2 2

Sample Output #2

Couldn't Produce!

Notes

Sample 1 Explanation:

There are $5$ regular customers, who can produce $2$ times the already produced quantity in one minute, and there are $3$ workers.

The minimum time required is $3$ minutes (producing $2^3=8$ units) to meet the requirements.

Sample 2 Explanation:

There are $2$ regular customers, who can produce $2$ times the already produced quantity in one minute, and there are $2$ workers.

Since no matter how long it takes, there will be $0$ units left, the output is Couldn't Produce!.

Note:

LiM is not a worker!

For each New Product, the number of regular customers is different.

For $20\%$ of the data, $T=1$, and all conditions are $\leqslant 100$.

For $100\%$ of the data, $T \leqslant 5000$, and all conditions are $\leqslant 5 \times 10^4$. $P$ is a prime number.

见题面 Input 部分

见题面 Output 部分