잔지바르의 거북이

거북이는 오래 산다. 잔지바르 섬의 거북이는 아예 죽지 않는다. 게다가 무성생식을 하고, 한 해에 많아야 한 마리를 낳는다. 그 밖에는 아무 일도 하지 않으며, 이 열대 낙원을 떠나지도 않는다.

잔지바르의 첫 거북이 잔지는 한 가지 일을 더 한다. 섬에 사는 거북이 수를 센다. 매년 새해 첫날에 거북이를 세어 수첩에 총 마리 수를 적는다. 여러 해가 지나면 수첩에는 1이 한 번 이상 이어진 다음 감소하지 않는 정수 수열이 남는다. (잔지도 아름다운 해변에서 알을 깨고 나온 뒤 가족을 이루기까지 시간이 걸렸다.)

어느 날 잔지는 배나 비행기를 타고 다른 곳에서 거북이가 들어왔을 수도 있다는 사실을 깨달았다. 그래서 섬에 사는 거북이 가운데 몇 마리가 잔지바르에서 태어나지 않았는지 궁금해졌다. 수첩만으로는 그 수의 하한밖에 알아낼 수 없다. 어떤 해의 거북이 수가 그 전해의 두 배보다 많다면, 그 차이는 전부 외부 유입으로 설명해야 하기 때문이다.

거북이가 1,000,000마리가 되는 순간 섬은 거북이로 가득 차고, 번식과 유입이 함께 멈춘다. 수첩에 적힌 수열이 주어질 때 밖에서 들어온 거북이 수의 하한을 구하는 프로그램을 작성하라.

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 각 테스트 케이스마다 다음이 주어진다.

• 공백으로 구분된 양의 정수 수열이 한 줄에 주어진다. 각 정수는 1,000,000 이하이고, 수열은 감소하지 않으며, 1이 한 번 이상 이어지면서 시작한다. 편의를 위해 수열 끝에 공백 하나와 0이 붙어 있다.

각 테스트 케이스마다 잔지바르에서 태어나지 않은 거북이 수의 하한을 정수 하나로 한 줄에 출력한다.