时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
有一天，恶魔们得到了一箱宝藏，箱子中有
枚金币。一共有
个恶魔，编号从
。编号最小的恶魔就是恶魔老大。 根据恶魔之间的规则，在分配财宝的时候，将会由恶魔老大提出分配方案。在方案提出后，所有恶魔对方案进行投票，包括恶魔老大在内。每一个恶魔都非常的贪婪，渴望得到尽可能多的金币，同时每一个恶魔又都非常的狡猾，他们都会选择对自己最有利的情况进行投票。如果一个方案
%及以上的恶魔投赞成票，那么该方案会被同意执行；否则，该方案不会被执行。 如果方案没有被执行，那么提出方案的恶魔老大将会被恶魔们杀死，他不配成为恶魔老大。剩下恶魔中编号最小的恶魔将会成为新的恶魔老大，然后重新按照上述规则，重新由新的恶魔老大提出新的方案进行操作，直到剩下最后一个恶魔或者有一个恶魔老大的方案被同意执行，那么分配结束。 现在让你作为编号为1的恶魔，你是恶魔老大，请问聪明的你要怎么样才能让自己在不被杀死的情况下获得最多的金币呢。
输入描述:
每个测试由几组输入数据组成。第一行包含一个整数—输入数据集的数量。
每组输入数据包含两个整数
输出描述:
请输出一个正整数表示你可以获得的最多金币的数量
备注:
注意数据的输入