Once upon a time, according to legend, King Hung had a very beautiful and lovely daughter who lived in the palace with her father. King Hung's daughter was of marriageable age, King Hung wanted to choose a worthy son-in-law for the princess. The young men who came to propose to the princess had to climb to the top of Tan Da mountain, the road to the top of Tan Da mountain had many obstacles, the young men who overcame each obstacle would receive gold coins. However, the young man wanted to receive coins at obstacle i only if he did not receive any coins at obstacle i-1.

To marry the princess, the young man had to overcome all obstacles to climb to the top of Tan Da mountain and collect as many gold coins as possible. Based on the number of coins at each obstacle, calculate the maximum number of coins that the young man could collect on the way to the top of Tan Da mountain.

Input: Input from the standard device has the following format:

• The first line contains an integer t, which is the number of testcases (1 ≤ t ≤ 10);
• Each testcase contains 2 lines:
  • The first line contains an integer N – the number of obstacles (0 ≤ N ≤ ~10^4~).
  • The second line contains N positive integers ~x_1, x_2, …, x_N~ ~(0 ≤ x_i ≤ 10^9)~. Where xi is the number of coins at the i-th obstacle that the boy encounters on the road.

Output: Print t lines to the standard device, each line is an answer for the testcase.

Exam:

Input

2
5
1 2 3 4 5
1
10

Output

9
10