$^{\text{∗}}$An array$b$is a subarray of an array$a$if$b$can be obtained from$a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

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

The first line of each testcase contains a single integer $n$ ($1 \le n \le 10$) — the length of the array $a$.

The second line of each testcase contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10$) — the elements of the array.

Output

For each testcase, output a single integer — the maximum average of any subarray of the given array.

It can be shown that the answer is always an integer.

Samples

3
4
3 3 3 3
5
7 1 6 9 9
5
3 4 4 4 3

3
9
4