It's the year 2050. Now, It hardly takes a few seconds to travel from one place to another. One of the future engineers is Akshay. Everyday he has to travel from his home to office. ( Yup, this situation has not changed at all )

The path from his home to office is a straight road with N traffic signals in between.

The time taken to travel from his home to the first traffic signal, first traffic signal to second traffic signal, second traffic signal to the third and so on are denoted by t₀,t₁,t₂...and so on. (with t_n denoting the time taken to travel from the last signal to his office)

All the signals are in synchronisation with one another. They become Green at the same time and again become Red at the same time.

All the lights stay Green for one second and Red for one second alternately.

Akshay starts driving from his home at time 0.

All the signals are Red at time 0 , remain Red for one second and then turn Green for one second and so on alternately.

Calculate the total time he spends daily to travel from home to office.

INPUT

The first line of input contains a single positive integer T denoting the number of test cases .
Each test case contains two lines.

First line contains a single integer N denoting the number of traffic signals.

Next line contains N+1 space separated positive integers t₀, t₁, t₂, t₃,...t_n

First integer denotes the time taken to travel between Akshay's home and the first signal, second integer deonotes the time taken to travel from the first signal and to second signal and so on.

OUTPUT

For each test case, calculate the total time taken by Akshay to travel from his home to office and print the answer in a new line.

CONSTRAINTS

1 ≤ T ≤ 100

0 ≤ N ≤ 1000

1 ≤ t_i ≤ 1000

(0 ≤ i ≤ N)