Stand on Zanzibar

Interview

Time limit1sMemory limit256 MB

Summary

The program adds yearly increases beyond twice the previous count to bound the number of imported turtles.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Turtles live long. The turtles on the island of Zanzibar never die at all. They also reproduce asexually, and each turtle gives birth to at most one child per year. Beyond that they do nothing, and they never leave their tropical paradise.

Zanzi, the first turtle on Zanzibar, does one more thing: it keeps track of how many turtles live on the island. Every New Year's Day it counts the turtles and writes the total in a small booklet. After many years the booklet holds a non-decreasing sequence of integers that begins with one or more ones. (Zanzi also needed some time after hatching on the beautiful beach before it started a family of its own.)

One day Zanzi realised that turtles from abroad might have arrived by boat or by plane. Now it wonders how many of the inhabitants were not born on Zanzibar. The booklet only yields a lower bound on that number. If the count in some year is more than twice the count of the year before, the whole difference has to be explained by import.

As soon as Zanzibar holds 1,000,000 turtles the island is completely covered, and both reproduction and import stop. Given the sequence from the booklet, write a program that computes the lower bound on the number of imported turtles.

Input

The first line contains an integer T, the number of test cases. Then, for each test case:

One line containing a sequence of space separated positive integers. Every integer is at most 1,000,000, the sequence is non-decreasing, and it starts with one or more ones. For convenience, a single space and a 0 are appended to the end of the sequence.

Output

For each test case, print one line containing a single integer: the lower bound on the number of turtles that were not born on Zanzibar.

Examples3

Example 1

Input

3
1 100 0
1 1 1 2 2 4 8 8 9 0
1 28 72 0

Expected output

98
0
42

Example 2
Input
```
1
1 0
```
Expected output
```
0
```
Example 3
Input
```
1
1 1 1 1 1 1 1 1 2 0
```
Expected output
```
0
```