사탕 공장

사탕 공장에 사탕을 만드는 방이 $n$개 있다. $n$은 홀수이고 $3 \le n \le 1001$이다. 방 하나는 사탕을 한 종류만 만들고, 방 번호는 1번부터 $n$번까지다.

1번 방은 최고의 사탕을 만든다. 이 특별한 사탕 한 알은 2번 방의 사탕 한 알과 3번 방의 사탕 한 알을 섞어서 만든다. 2번 방의 사탕 한 알도 4번 방과 5번 방의 사탕을 각각 한 알씩 섞은 것이고, 3번 방의 사탕 한 알은 6번 방과 7번 방의 사탕을 각각 한 알씩 섞은 것이다. 정리하면 $i$번 방($1 \le i \le \lfloor n/2 \rfloor$)은 $2i$번 방의 사탕 한 알과 $2i+1$번 방의 사탕 한 알을 재료로 써서 자기 사탕 한 알을 만든다. 그래서 1번 방의 최고의 사탕에는 모든 종류의 사탕이 들어간다.

각 방은 재료가 허용하는 한 최대로 만든다. 즉 $i$번 방이 만드는 개수는 $2i$번 방과 $2i+1$번 방에 남아 있는 사탕 개수로 정해진다. 방이 3개인 공장을 보자. 2번 방이 5알, 3번 방이 7알을 만들었다면 1번 방은 최고의 사탕을 5알 만든다. 그러면 3번 방에 사탕 2알이 남고 2번 방에는 하나도 남지 않는다. 이때 공장이 만든 사탕은 모두 7알이다.

$\lfloor n/2 \rfloor + 1$번 방부터 $n$번 방까지는 재료 없이 사탕을 만들고, 각 방이 만든 개수를 알려 준다. 이 공장이 만든 사탕이 모두 몇 알인지 구하라. 전체 개수는 각 방이 만든 사탕을 모두 더한 뒤, $i$번 방의 재료로 쓴 $2i$번 방과 $2i+1$번 방의 사탕을 빼서 센다.

첫 줄에 테스트 케이스 개수가 주어진다. 이어서 테스트 케이스마다 두 줄이 주어진다. 첫 줄에는 공장의 사탕 제조실 개수 $n$이 주어지고, 둘째 줄에는 $\lfloor n/2 \rfloor + 1$번 방부터 $n$번 방까지 각 방이 만든 사탕 개수가 방 번호 순서대로 주어진다. 값은 모두 $\lfloor n/2 \rfloor + 1$개다. 다음 두 줄씩이 그다음 테스트 케이스다.

테스트 케이스 개수만큼 줄을 출력한다. 각 줄에 그 테스트 케이스에서 공장이 만든 사탕이 모두 몇 알인지 출력한다.