A Beautiful Array

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Little Tinu is a handsome kid and likes only beautiful things. He has an array and wants its most beautiful permutation. The beauty of a 1-indexed array A is defined as:

$\text{[math]}$ where $\text{[math]}$ is integer division.

输入描述:

The first line contains T(1 ≤ T ≤ 10), the number of test cases. Every test case contains 2 lines. First line has an integer N(1 ≤ N ≤ 10³), the size of the array A. Second line contains the array A as space separated integers(0 ≤ A_i ≤ 10⁶).

输出描述:

Output for each test case, the maximum beauty of any permutation of the array A.

示例1

输入

复制

输出

复制

2
69

备注:

Sample test case 1: 
There are 6 permutations possible: 
 Beauty  = 2 
 Beauty  = 1 
 Beauty  = 1 
 Beauty  =  - 1 
 Beauty  =  - 1 
 Beauty  =  - 2 
Maximum of all beauties is 2. 
Sample test case 2: 
The best permutation is [1, 40, 70, 40] where beauty is 69.