问题描述

新的一学期开始了，来自天南地北的同学们又陆陆续续回到了学校，这次大家都带来了各种风味小吃，与同窗好友共分享。翠花当然也不例外，他带来了不少的饲料。

不过，一个多月过去了，其他同学带来的糖果零食都陆陆续续吃完了，唯独翠花的饲料还剩满满一袋，不仅没有减少的迹象，反而似乎还比刚来的时候多了些。这让翠花很是着急，再美味的食物，一旦存放过久，都会变质，变质的饲料就只能丢掉，这实在是一种浪费……一向都很节俭的翠花决不允许这种事情的发生，所以他决定弄清楚饲料无法吃完的原因。

终于他找到了答案，原来这种神奇的饲料每隔 $M$ 天会发生一次分裂，也就是说，原本 10 斤的饲料在 $M$ 天后会变成 20 斤。难怪总是吃不完了！找到原因以后，问题就好解决了，现在还剩下 $N$ 斤饲料，而离饲料变质还有 $K$ 天，翠花想知道，平均每天他至少要吃多少饲料（吃掉的饲料是不会分裂的），才能在饲料变质之前全部吃完？

注意由于翠花的秤是整数刻度的，所以他每天吃的饲料斤数也只能是整数。

例如，现在还剩 10 斤饲料，而离饲料变质只有 5 天，饲料每 2 天发生一次分裂，那么他如果每天吃 3 斤饲料，结果将无法把饲料全部吃完：

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

可见第 3 天饲料就全部吃完了，因此对于上面的情况，翠花每天至少要吃 4 斤才能实现目标。

你的任务就是对于给定的 $N$，$M$，$K$，计算翠花每天至少要吃多少斤饲料？

输入格式

第 1 行只包含一个整数 $T$（$0 < T \leq 10000$），表示一共有 $T$ 组测试数据。

从第 2 行到第 $T + 1$ 行每行包含三个整数 $N$，$M$，$K$，为一组测试数据。$0 < N, M, K \leq 100$。

输出格式

共 $T$ 行，每行对应一组测试数据的答案（将第 $I$ 组测试数据的答案输出在第 $I$ 行）。

每组测试数据的答案只包含一个整数，为翠花每天最少吃多少斤饲料。

样例输入

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

样例输出

4
2
3
1
6
100

提示

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