정원의 골칫거리, 그 후

빈첸티 씨는 정원을 가꾸는 일을 몹시 싫어하기로 유명한 정원 주인이다. 지난번 낙엽 소동이 지나가고 얼마 뒤, 봄이 오면서 새로운 골칫거리가 생겼다. 정원 곳곳에 잡초가 무성하게 자라기 시작한 것이다. 어느 날 빈첸티 씨는 작업실에서 오랜 시간을 보낸 끝에 휴대용 화염방사기를 들고 정원에 나섰다.

정원은 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 구역으로 이루어져 있다. $i$번 구역에는 정수 개수의 잡초 $c_i$가 있다. 화염방사기를 $i$번 구역에 한 번 사용하면 $i$번 구역과 양옆의 $i-1$번, $i+1$번 구역의 잡초 수가 각각 절반으로 줄어든다.

여기서 "절반으로 줄어든다"는 것은 $2$로 나눈 몫(내림)을 뜻한다. 즉 잡초가 $8$개이면 $4$개가 되고, $5$개이면 $2$개가 된다. 화염방사기는 존재하지 않는 $0$번 구역이나 $N+1$번 구역을 겨냥할 수도 있는데, 이때는 각각 $1$번 구역만, 또는 $N$번 구역만 줄어든다.

모든 구역의 잡초를 $0$개로 만들기 위해 빈첸티 씨가 화염방사기를 최소 몇 번 사용해야 하는지 구하여라.

첫째 줄에 테스트 케이스의 개수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 정원의 구역 수 $N$ ($1 \le N \le 10^6$)이 주어진다. 둘째 줄에는 각 구역의 잡초 수를 나타내는 $N$개의 정수 $c_i$ ($0 \le c_i \le 10^6$)가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 화염방사기를 최소 몇 번 사용해야 하는지를 한 줄에 하나씩 출력한다.