题目描述
Bessie 正在试验一种能够产生巨大冲击波的强大的蹄部植入物。她有 （）块砖块排开在面前，分别需要至少 的力量才能击破（）。
Bessie 可以通过击打特定的砖块来施加力量，但由于她的植入物的奇特性质，它不会对她所击打的那块砖块施加任何力量。相反，如果她选择击打砖块 一次，其中 是一个 范围内的整数，对所有在 范围内的整数 ，它将对砖块 施加 的力量。同时这个力量是累积的，因此对一块砖块施加两次 的力量将对该砖块施加总共 的力量。
请求出击破所有砖块所需要的最少击打次数。
输入格式
输入的第一行包含 （），为测试用例的数量。
第 行包含一个整数 ，为测试用例 中的砖块数量。
第 行包含 个空格分隔的整数 ，表示砖块 需要 的力量才能击破。
输入保证一个测试点中的所有 之和不超过 。
输出格式
输出 行，第 行包含第 个测试用例的答案。
样例
输入
6 5 0 2 4 5 8 5 6 5 4 5 6 5 1 1 1 1 1 5 12 10 8 6 4 7 6 1 2 3 5 8 13 2 1000000000000000000 1000000000000000000
输出
2 3 2 4 4 2000000000000000000
提示说明
【样例解释】
在第一个测试用例中，Bessie 通过两次击打击破所有砖块的唯一方法是击打砖块 两次，施加总力量分别为 。
在第二个测试用例中，Bessie 通过三次击打击破所有砖块的一种方法是分别击打砖块 ， 和 一次，施加总力量分别为 。
在第三个测试用例中，Bessie 通过两次击打击破所有砖块的一种方法是分别击打砖块 和 一次，施加总力量分别为 。
【数据规模与约定】
- 测试点 2：所有 均相等。
- 测试点 3-6：。
- 测试点 7-14：没有额外限制。