Practice on Toph

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

Groot's Mission

Limits: 1s, 512 MB

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?

Input

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

Output

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

Samples

InputOutput
1
5
2 1 3 5 4
4

Author
Discussion
Submit

Login to submit