P4028 New Product

A magical story about doing business... (Friendly reminder: mind the time limit!).

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.

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.

For each New Product: - If it is achievable, output the minimal number of minutes worked. - If it is not achievable, output `Couldn't Produce!`.

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