找出伪币

题目描述

给你一个装有 $n$ 枚硬币的袋子。$n$ 枚硬币中有一个是伪造的,并且那个伪造的硬币和真的硬币重量不一样。你的任务是找出这枚伪造的硬币。 为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,比如天平。利用这台仪器,可以知道两组硬币的重量是否相同。

输入输出格式

输入格式


第一行,一个正整数 $T$,表示有 $T$ 组数据。 接着 $T$ 行,每行三个正整数 $k,p,n$。 $p=-1$:伪币偏轻;$p=1$:伪币偏重;$p=0$:你不知道伪币与真币的重量对比关系。 $n$ 为一个 $k$ 位十进制正整数(没有前导 $0$)。

输出格式


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

输入输出样例

输入样例 #1

2
1 1 6
1 0 6

输出样例 #1

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$ 时,你还需要知道伪币与真币相比是轻是重