SP21834 SACITY - Sadde and His City

Sadde owns a country named as Sadde land. In Sadde land each city consists of only one row of building. Sadde being the king wanted to know the score of cities in his country. Sadde gives the task of scoring to one of his minister Dukker. Each city consists of “N” buildings in a single row and each building is having a container in front of them. For each building in the city Dukker calculate the number of buildings having less height in left of that building(say **Hmin $ _{i} $** ) and number of buldings having greater height in right of that building(say **Hmax $ _{i} $** ). He put **Hmin $ _{i} $ + Hmax $ _{i} $** number of flags in container of **i $ ^{th} $** building. He took all containers from the buildings and shuffles them. Now he wants to distribute flags among buildings of city such that each building should get same number of flag and a building will get all the flags from single container. Score of city is the maximum number of flags that a building can have.

Input consist of **T** number of test cases. Each case contains two lines. First line contains **N** denoting number of building in a city. Second line will contain **N** integers denoting **H** $ _{i} $ (height of building).

Output should contain **T** line denoting score of that city.