Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Avengers team sent Groot and Rocket in a reconnaissance mission at RUET. However, Rocket got busy in eating mangoes as soon as he found the mango shop inside RUET! So, Groot has to finish the mission by himself. He asked Tony Stark for help. Stark mapped Ruet in a 1-D array **A** in such a way that Groot can finish his mission by starting his journey from the **1st** position of the array and finishing on **N-th** position of the array. The array holds energy level **A[i]** in **i-th** position. Groot can use this energy and traverse the array by jumping **X** step **(X ≤ A[i], 1 ≤ i ≤ N)** from **i-th** position of the array. In each jump Groot uses **X** amount of energy. Now, he wants to **minimize** the total energy required to travel from the **1st** position to the **N-th** position of the array so that he can finish his mission.

Groot met you at RUET main gate and learned that you are a great programmer. So, he asked you to help him find out what is the minimum total energy required for him to finish his mission. Can you help him?

There will be **T** test cases. In each case, there will be 2 lines. The first line in each case contains an integer **N** , the length of the array **A**. The next line will contain **N** space separated integer denoting the array **A**.

**1 ≤ T ≤ 100****1 ≤ N ≤ 1000****1 ≤ A[i] ≤ 1000**

For each test case print a single integer **Z** in a line, the total minimum energy required for Groot to finish his mission.

Input | Output |
---|---|

1 5 2 1 3 5 4 | 4 |

Login to submit