In this problem we will be looking for medians of data set. Median is the central element in ordered data group. For example: for the set {2, 6, 3, 3, 2} the median would be 3. In general, if we have n elements {a1, a2, a3 ... an}, we define the median as element a_(n+1)/2 if n is odd and (a_n/2+a_n/2+1)/2 otherwise.

You will be given N numbers and you must calculate N medians. i-th median is taken on the subset [a₁, a₂, a₃ ... a_i] for 1 ≤ i ≤ N.

Input

The first line contains the number of test cases. Each case consists of an integer N (1 ≤ N ≤ 100000). N integers a_i (0 ≤ a_i < 2³¹) follow, elements in data set.

Output

For each case, print N lines with the medians. If the result is non-integral, print the exact value using decimal point (see example).

Example

Input:
2
4
3 5 7 3
2
3 4
Output:
3
4
5
4
3
3.5