【题目描述】

海龟寿命长（而且兴旺发达）。桑给巴尔岛上的海龟甚至是不朽的。此外，他们每年最多生一个孩子。除此之外，他们什么也不做。他们从未离开过他们的热带天堂。

桑给巴尔岛上的第一只海龟桑兹有一项活动：它跟踪岛上海龟的数量。每年元旦，它都会清点海龟，并将总数写在一本小册子上。多年后，这本小册子包含了一个非递减的整数序列，从一个或多个整数开始。（桑给巴尔美丽的海滩上，桑兹从卵里出来后，花了一段时间独自组建了一个家庭。）

有一天，桑兹意识到，从国外来桑给巴尔的海龟也可能是乘船或飞机。现在，人们想知道有多少居民不是桑给巴尔人。不幸的是，它只能从小册子中的顺序得出一个下限。事实上，如果一年中海龟的数量是前一年的两倍多，那么这种差异必须通过进口来充分解释。

桑给巴尔岛最多容纳100万只海龟，如果超过100万只海龟，繁殖和进口都停止了。请帮帮桑兹！编写一个程序，计算输入海龟的下限，给定一个序列，如上所述。

【输入】

输入第一行一个整数T（1≤T≤13），表示测试用例的数量。

以下T行，每行输入以空格分隔的正整数非递减序列（≤1000000），每行以1开始。以0 结束。

【输出】

对于每个测试用例，输出一行包含一个整数：即桑给巴尔出生的海龟数量的下限。

【样本输入1】

3

1 100 0

1 1 1 2 2 4 8 8 9 0

1 28 72 0

【样本输出1】

98

0

42