Optimal Facility Placement

You are given a city with houses aligned along a straight line at unit distances. The city council plans to build a facility such that the maximum walking distance from any house to the facility is minimized. In other words, if the houses are numbered sequentially from 0 to \(n-1\), and the facility is placed at house \(k\), then each house \(i\) has a walking distance of \(|i-k|\). Your task is to choose an optimal \(k\) that minimizes \(\max\{|i-k| : 0 \le i < n\}\).

Note that although each test case provides the number of inhabitants for each house, these numbers do not affect the optimal position. Essentially, the answer for a test case with \(n\) houses is \(\lfloor n/2 \rfloor\).

inputFormat

The input begins with an integer \(t\) representing the number of test cases. Each test case is described in two lines:

• The first line contains an integer \(n\) indicating the number of houses.
• The second line contains \(n\) integers, where each integer represents the number of inhabitants in a house (this information is not used in the computation).

outputFormat

For each test case, output a single integer on a new line: the minimum possible value of the maximum walking distance when the facility is placed optimally.

## sample

3
3
1 2 3
4
4 1 3 2
5
1 1 1 1 1

1
2
2

</p>