Description

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.

Input Format

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 Format

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

2
1 1 6
1 0 6

2
3

Hint

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