E. Total Gold
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sherbiny has set sail on a grand pirate conquest! He attacks a new island every day for $$$n$$$ days. Brook stands at the bow of the ship, playing a victorious tune on his violin.

On day $$$i$$$, Sherbiny loots $$$a_{i}$$$ pieces of gold. Brook wants to write a song about the crew's massive fortune.

Find the total amount of gold Sherbiny has collected after all $$$n$$$ days so Brook can finish his masterpiece.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \times 10^{5}$$$) — the number of days.

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \dots, a_{n}$$$ ($$$0 \le a_{i} \le 10^{9}$$$) — the gold found on each day.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$.

Output

For each test case, output one integer — the total amount of gold Sherbiny gets.

Example
Input
3
1
7
5
1 2 3 4 5
4
0 10 0 20
Output
7
15
30
Note

In the second test case, Sherbiny gains $$$1+2+3+4+5=15$$$ gold coins.