P1431 Find the Counterfeit Coin

You are given a bag containing $n$ coins. Among the $n$ coins, exactly one is counterfeit, and its weight is different from that of a genuine coin. Your task is to find this counterfeit coin. To help you, you are given a device that can compare the weights of two groups of coins, e.g., a balance scale. Using this device, you can tell whether the two groups have the same total weight.

The first line contains a positive integer $T$, the number of test cases. Then follow $T$ lines, each containing three positive integers $k,p,n$. $p=-1$: the counterfeit coin is lighter; $p=1$: the counterfeit coin is heavier; $p=0$: you do not know whether the counterfeit coin is lighter or heavier. $n$ is a $k$-digit positive decimal integer (with no leading $0$).

Output $T$ lines, each containing an integer $m$, the minimum number of weighings that guarantees finding the counterfeit coin.

For $40\%$ of the testdata, $n\leq 10^5$. For $100\%$ of the testdata, $k\leq 10^4$, $3\lt n\lt 10^{10001}$, $1\leq T\leq 40$. When $p=0$, you also need to determine whether the counterfeit coin is lighter or heavier than a genuine one. Translated by ChatGPT 5