K. Cookies
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ kids standing in a line, indexed from $$$1$$$ to $$$n$$$. Each kid $$$i$$$ has a rating $$$r_i$$$. You need to distribute cookies to these kids such that the following conditions are met:

  1. Each kid must receive at least one cookie.
  2. If kid $$$i$$$'s rating is strictly greater than kid $$$i-1$$$'s rating (i.e., $$$r_i \gt r_{i-1}$$$), then kid $$$i$$$ must receive strictly more cookies than kid $$$i-1$$$.
Your task is to find the minimum total number of cookies required to satisfy these conditions.
Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$), representing the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$), representing the number of kids.

The second line contains $$$n$$$ space-separated integers $$$r_1, r_2, \ldots, r_n$$$ ($$$1 \le r_i \le 1000$$$), representing the ratings of the kids.

Output

For each test case, output a single integer: the minimum total number of cookies required to satisfy all conditions.

Example
Input
2
3
1 2 3
3
3 2 1
Output
6
3