SOLVE
LATER
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_{0},t_{1},t_{2}...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_{0}, t_{1}, t_{2}, t_{3},...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)
In the first case there is only one traffic signal.
He starts at time zero and reaches traffic signal at time 2 seconds.
He has to wait a second as traffic signal goes green at time 3 seconds.
Now moving ahead he takes 3 seconds more to reach from traffic signal to office. Thus total time is 6 seconds.
Similarly for second test case he only waits for 1 second (at the third signal) , so total time taken will be 36 seconds.
Participants are requested to keep themself updated with the announcements of the contest.