A. Beautiful Average

You are given an array 𝑎

 of length 𝑛

.

Your task is to find the maximum possible average value of any subarray

∗

 of the array 𝑎

.

Formally, for any indices 𝑙,𝑟

 such that 1≤𝑙≤𝑟≤𝑛

, define the average of the subarray 𝑎

𝑙

,𝑎

𝑙+1

,…,𝑎

𝑟

 as the sum of elements divided by the number of elements or:

𝚊𝚟𝚐(𝑙,𝑟)=1

𝑟−𝑙+1

∑

𝑖=𝑙

𝑟

𝑎

𝑖

Output the maximum value of 𝚊𝚟𝚐(𝑙,𝑟)

 over all choices of 𝑙,𝑟

.

∗

An array 𝑏

 is a subarray of an array 𝑎

 if 𝑏

 can be obtained from 𝑎

 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 𝑡

 (1≤𝑡≤10

4

) — the number of test cases.

The first line of each testcase contains a single integer 𝑛

 (1≤𝑛≤10

) — the length of the array 𝑎

.

The second line of each testcase contains 𝑛

 integers 𝑎

1

,𝑎

2

,…,𝑎

𝑛

 (1≤𝑎

𝑖

≤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.

Example

Input

Copy

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

Output

Copy

3
9
4