小苯面前有 个容量无限的水瓶，目前第 个瓶子目前装了 水量的水。他可以使用以下操作至多倒出 单位的水： 选择两个不同的水瓶 ，再将 瓶中任意正整数量的水倒入 瓶。（前提是倒出来的水不超过 瓶中还剩下的水。） （形式化的：选择任意正整数 ，执行：；其中 表示赋值操作，同时需要保证所有此操作中 的和不超过 。） 此外，小苯还有有一个装了 单位水量的水壶，他可以将水壶中的水倒进任意水瓶任意次，前提是倒入的水量也必须是正整数，同时总共不能倒出超过 单位水量。 小苯操作完后，会从所有水瓶中选择一瓶水量最小的水喝掉，他想知道他最多可以喝掉多少水，请你帮他算一算吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：第一行输入三个正整数 ，分别表示水瓶的个数，可以互相之间倒水的总量，和额外的水壶中的水量。第二行 个正整数 ，表示每瓶水目前所装的水量。（保证同一个测试文件中的测试数据里 的总和不超过 。）

输出描述:

对于每组测试数据，在单独的一行输出一个整数表示答案，表示小苯喝掉的水的最大量。