Migrated from Lutece 766 乐乐和球球

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

乐乐和岳航君在玩儿一个奇怪的游戏。

他们拿了$N$个一模一样的罐子，还有$K$个一模一样的小球，每个罐子里可以放下任意数量的小球，但是罐子外表被涂黑了，从外边观察是看不到每个罐子里有几个小球的。

岳航君在游戏之前可以自己选择如何把$K$个小球分配到$N$个罐子里面去，但是分配之后，邪恶的乐乐会把罐子的顺序随机打乱。这样哪个罐子里有几个小球就不是那么容易分辨出来了。

岳航君每次可以指向一个罐子，乐乐会打开这个罐子，如果里面是空的，乐乐会告诉岳航君，如果里面有球，乐乐就会拿出一个球，再把罐子盖上，注意这个时候，乐乐不会告诉岳航君罐子里还剩几个球。

岳航君希望能在最坏情况下用尽量少的次数，拿出$C$个球出来。为了完成这个目的，他需要在游戏开始的时候，想一个优越的分配方法，告诉岳航君最坏情况下的最少次数是多少吧！

Input

第一行一个整数$T$ ($T\leq 20$)，代表数据组数。

每组数据由一行组成，包括三个整数$N$，$K$和$C$（$1\leq C\leq K\leq 1000000, 1\leq N\leq 1000000$)，意义如题面所示。

Output

输出$T$行，每行输出最少的步数。

Samples

2
3 6 4
3 4 4

4
5

Note

第一组样例：一个可行的方案是三个罐子各放$2$个球，然后任选两个罐子各拿$2$次。

第二组样例：一个可行的方案是一个罐子为空罐，另外两个罐子各放两个球。这时，如果第一次运气不好指向了空罐子，接下来只需在剩下的两个罐子里每个罐子各拿$2$次就可以了，所以无论如何，总步数不会超过$5$次。

Resources

第五届ACM趣味程序设计竞赛第三场（正式赛）