Problem 1031. -- Feed

1031: Feed

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

新的一学期开始了,来自天南地北的同学们又陆陆续续回到了学校,这次大家都带来了各种风味小吃,与同窗好友共分享。翠花当然也不例外,他带来了不少的饲料。
不过,一个多月过去了,其他同学带来的糖果零食都陆陆续续吃完了,唯独翠花的饲料还剩满满一袋,不仅没有减少的迹象,反而似乎还比刚来的时候多了些。这让翠花很是着急,再美味的食物,一旦存放过久,都会变质,变质的饲料就只能丢掉,这实在是一种浪费……一向都很节俭的翠花决不允许这种事情的发生,所以他决定弄清楚饲料无法吃完的原因。
终于他找到了答案,原来这种神奇的饲料每隔M天会发生一次分裂,也就是说,原本10斤的饲料在M天后会变成20斤。难怪总是吃不完了!找到原因以后,问题就好解决了,现在还剩下N斤饲料,而离饲料变质还有K天,翠花想知道,平均每天他至少要吃多少饲料(吃掉的饲料是不会分裂的),才能在饲料变质之前全部吃完?
注意由于翠花的秤是整数刻度的,所以他每天吃的饲料斤数也只能是整数。
例如,现在还剩10斤饲料,而离饲料变质只有5天,饲料每2天发生一次分裂,那么他如果每天吃3斤饲料,结果将无法把饲料全部吃完:

注意在第二天,他白天吃掉3斤变成还剩4斤,然后饲料会在晚上发生分裂,最终变成剩8斤。由于在第五天结束的时候还剩1斤没有吃掉,因此每天吃3斤是不够的。如果他改成每天吃4斤,那么:

可见第3天饲料就全部吃完了,因此对于上面的情况,翠花每天至少要吃4斤才能实现目标。
你的任务就是对于给定的N,M,K,计算翠花每天至少要吃多少斤饲料?

Input

第1行只包含一个整数T(0<T≤10000),表示一共有T组测试数据。
从第2行到第T+1行每行包含三个整数N,M,K,为一组测试数据。0<N、M、K≤100。

Output

共T行,每行对应一组测试数据的答案(将第I组测试数据的答案输出在第I行)。
每组测试数据的答案只包含一个整数,为翠花每天最少吃多少斤饲料。

Sample Input

6
10 2 5
6 10 3
12 4 6
48 26 100
100 10 100
100 1 1

Sample Output

4
2
3
1
6
100

HINT

使用C++的选手请注意:本题测试数据很多,输入输出建议使用scanf和printf函数,经测试处理大量数据时其速度明显快于cin和cout。

Source

[Submit][Status]