Sau thời gian dài nghiên cứu, Bessie đã tìm ra được một thuật toán sắp xếp mới, được trình bày như sau: Tìm số nhỏ nhất trong những phần tử đã có, loại bỏ nó là thêm nó vào cuối của mảng.

Cô có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) phần tử cần sắp xếp được kí hiệu là \(a_1, a_2, \ldots, a_N\) (\(1 \leq a_i \leq 10^{11}\)) và cô mất \(p\) giây để tìm ra phần tử nhỏ nhất trong \(p\) phần tử.

Nông dân John muốn giúp đỡ Bessie nên đã tuyển vài con bò để giúp Bessie hoàn thành công việc nhanh hơn, tuy nhiên chúng khá là lười biếng. Bessie thông minh đã nghĩ ra cách để tận dụng sự lười biếng của chúng: Cô chia những phần tử cần sắp xếp thành hai nửa, một nửa cô xử lý và phần còn lại giao cho những trợ lý của mình. Với mỗi phần tử mà Bessie xử lý, cô sử dụng thuật toán của mình như bình thường. Còn với những phần tử do các trợ lý đảm nhiệm, cô giao cho mỗi con bò trợ lý một phần tử quy định. Điều này có vẻ vô lý nhưng lại thuyết phục vì nông trại của nông dân John có rất nhiều bò nên có thể cho cô bao nhiêu trợ lý tùy thích. Mỗi con bò sau khi nhận được phần tử của mình sẽ được cho phép đi ngủ trong \(a_i\) giây, sau đó thêm nó vào cuối mảng sắp xếp khi chúng tỉnh giấc. Do Bessie là người chỉ đạo, khi cô và một con bò cùng thêm phần tử vào mảng một lúc, cô sẽ được ưu tiên đặt vào trước. Nếu nhiều hơn một trợ lý được đưa cho cùng một phần tử, chúng sẽ thêm vào mảng cùng một lúc.

Hãy giúp Bessie chia những phần tử để đảm bảo hoàn thành mảng sắp xếp trong thời gian ngắn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(T\) là số lượng các test case (\(1 \leq T \leq 10\)).
• Mỗi bài test case bao gồm:
  • Dòng đầu tiên chứa số lượng phần tử \(N\) trong mảng cần sắp xếp.
  • Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, …, a_N\) là những phần tử Bessie cần sắp xếp. Một số có thể xuất hiện nhiều lần.

Output

• Gồm \(T\) dòng, mỗi dòng gồm một số nguyên là thời gian ngắn nhất Bessie cần để sắp xếp lại mảng.

Scoring

• Subtask 1: \(N \leq 16\)
• Subtask 1: \(N \leq 150\)
• Subtask 1: \(\sum N≤5000\)
• Subtask 1: Không có ràng buộc gì thêm

Example

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

6
15
5
6