#P1431. 找出伪币

找出伪币

题目描述

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

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

输入格式

第一行,一个正整数 TT,表示有 TT 组数据。

接着 TT 行,每行三个正整数 k,p,nk,p,n

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

nn 为一个 kk 位十进制正整数(没有前导 00)。

输出格式

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

2
1 1 6
1 0 6
2
3

提示

对于 40%40\% 的数据,n105n\leq 10^5

对于 100%100\% 的数据,k104k\leq 10^43<n<10100013\lt n\lt 10^{10001}1T401\leq T\leq 40

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