Description

樱井景和是刚毕业的一名大学生，他有着世界和平的梦想。

在经过一次失败的面试之后，在面馆吃面时，他意外地卷入了欲望大奖赛。

他遭受了邪魔徒的攻击，在逃跑途中，遇到了作为假面骑士极狐的浮世英寿。

极狐正在准备直接消灭邪魔徒的飞船总部。

飞船总部内有 个邪魔徒需要消灭，第 个邪魔徒的血量为 。

极狐准备用骑士踢解决他们，请问他骑士踢的攻击力最小需要是多少？

注：若极狐的骑士踢的攻击力 ，就可以消灭第 个邪魔徒。

Input Format

第一行一个整数 ，表示测试数据组数。 接下来是 组测试数据。 ​ 每组测试数据共两行，第一行一个整数

表示邪魔徒的数量。

第二行为 个整数，第 个整数为 表示第 个邪魔徒的血量。 数据保证 。

Output Format

对于每组测试数据，输出一行一个整数，表示极狐的骑士踢的最小攻击力。

1
3
1 2 3​

3