Description

LiM owns a handmade pastry shop. Because the pastries are both affordable and delicious, the shop has accumulated $P$ regular customers ($P$ is prime).

Every time the shop launches a New Product, they make many items. All $P$ customers will support it in this way:

• Each customer buys the same quantity.
• They buy as much as possible.

The shop has $B$ workers. At the end of each minute, the total number of products becomes $A$ times the current total.

(Note: initially, there is one already-made New Product as a sample.)

After production is finished and the $P$ regular customers rush to buy (only these regular customers are considered):

• To take care of the workers, exactly $B$ items must remain.

Given the known conditions, please help LiM compute the minimal working time.

Input Format

There are $T+1$ lines.

The first line contains an integer $T$, the number of New Products.

Lines $2$ to $T+1$ each contain three integers $P$, $A$, $B$, as described above.

Output Format

For each New Product:

• If it is achievable, output the minimal number of minutes worked.
• If it is not achievable, output Couldn't Produce!.

1
5 2 3

3

1
2 2 2

Couldn't Produce!

Hint

Sample 1 explanation: There are $5$ regular customers, the total multiplies by $2$ each minute, and there are $3$ workers. The minimum is $3$ minutes (produce $2^3 = 8$ items) to meet the requirement.

Sample 2 explanation: There are $2$ regular customers, the total multiplies by $2$ each minute, and there are $2$ workers. Since no matter how long they work the leftover will always be $0$, output Couldn't Produce!.

Notes:

• LiM is not a worker.
• For each New Product, the number of regular customers may differ.

Constraints:

• For $20\%$ of the testdata, $T = 1$ and all values $\leqslant 100$.
• For $100\%$ of the testdata, $T \leqslant 5000$, all values $\leqslant 5 \times 10^4$, and $P$ is prime.

Translated by ChatGPT 5