题目描述

给你一个装有 $n$ 枚硬币的袋子。$n$ 枚硬币中有一个是伪造的，并且那个伪造的硬币和真的硬币重量不一样。你的任务是找出这枚伪造的硬币。

为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。

输入格式

第一行，一个正整数 $T$，表示有 $T$ 组数据。

接着 $T$ 行，每行三个正整数 $k,p,n$。

$p=-1$：伪币偏轻；$p=1$：伪币偏重；$p=0$：你不知道伪币与真币的重量对比关系。

$n$ 为一个 $k$ 位十进制正整数（没有前导 $0$）。

输出格式

输出 $T$ 行，每行一个整数 $m$，表示至少要称量 $m$ 次就一定能找出伪币。

2
1 1 6
1 0 6

2
3

提示

对于 $40\%$ 的数据，$n\leq 10^5$。

对于 $100\%$ 的数据，$k\leq 10^4$，$3\lt n\lt 10^{10001}$，$1\leq T\leq 40$。

当 $p=0$ 时，你还需要知道伪币与真币相比是轻是重