문제

거북이는 오래 삽니다. (그리고 번영하죠.) 잔지바르의 거북이는 심지어 영생합니다. 번식에 관심이 없는 무성 동물로, 매년 최대 한 명의 자손만 낳죠. 그 외에는 아무런 일도 하지 않습니다. 열대 천국을 절대 떠나지도 않죠.

잔지바르의 첫 거북이인 잔지 바르는 또 다른 일을 합니다: 섬의 거북이의 수를 세는 것입니다. 매 새해마다 바르는 거북이의 수를 세고 작은 책자에 기록합니다. 꽤 많은 해가 지나고 이제 책자에는 1 또는 몇 개의 1로 시작하는 감소하지 않는 정수 수열이 적혀 있습니다. (잔지바르의 아름다운 해변에서 태어난 후, 바르가 가족을 시작하기까지는 시간이 걸렸습니다.) 

어느 날 바르는 거북이가 잔지바르로 배나 비행기를 타고 해외에서 유입될 수도 있음을 깨달았습니다. 이제 바르는 얼마나 많은 거북이가 잔지바르에서 태어나지 않았을지 궁금합니다. 안타깝게도 책자의 수열을 통해 하한값밖에 알 수 없습니다. 그 해 거북이의 수가 이전 해의 두 배 이상이라면, 당연히 차는 모두 유입으로 해석됩니다.

잔지바르의 거북이가 1,000,000마리에 달하면 섬이 거북이로 뒤덮이므로 번식 및 유입 과정이 모두 중지됩니다. 바르를 도와줍시다! 수열이 주어질 때, 문제에 제시된 유입된 거북이의 수의 하한값을 계산합시다.

입력

입력은 테스트 케이스의 수를 나타내는 하나의 정수 T가 한 줄에 주어지며 시작됩니다. 각 테스트 케이스는 아래와 같습니다:

- 1 또는 여러 개의 1로 시작하는 공백으로 구분된 양의 정수(<= 1,000,000)의 감소하지 않는 수열. 편의를 위해, 하나의 공백과 하나의 0이 수열 끝에 추가됨.

출력

각 테스트 케이스에 대해, 하나의 정수를 출력합니다: 이는 잔지바르에서 태어나지 않은 거북이의 수의 하한값입니다.