Alice đang mời bạn bè đến dự một bữa tiệc ăn bánh ngọt. Tuy nhiên, không phải tất cả bạn bè đều ở cùng một địa điểm, vì vậy mọi người phải tập trung tại cùng một điểm trước.
Alice có \(n\) bạn, bạn thứ \(i\) ở vị trí \({a_i}\). Để mọi người đều có mặt ở cùng một chỗ, Alice phải thực hiện nhiều cuộc gọi nhóm. Thật không may, tín hiệu yếu, và Alice chỉ có thể gọi cho \(2\) người khác cùng một lúc.
Là một người tốt bụng, Alice không muốn bạn bè mình phải đi bộ quá xa. Vì vậy, với mỗi cuộc gọi nhóm có người bạn thứ \(i\) và người bạn thứ \(j\), Alice sẽ bảo cả hai người gặp nhau tại một vị trí số nguyên nào đó nằm giữa hai điểm \(min({a_i}, {a_j})\) và \(max({a_i}, {a_j})\). Sau đó, cả hai sẽ di chuyển đến vị trí đó nhanh đến mức Alice không thể thực hiện cuộc gọi nhóm nào trong suốt quá trình di chuyển. Xin lưu ý rằng Alice có thể gọi lại cho những người bạn này khi họ đến vị trí đó.
Bữa tiệc sắp bắt đầu nên Alice cần thực hiện các cuộc gọi nhóm thật nhanh. Giúp cô ấy tìm số lượng cuộc gọi nhóm tối thiểu mà cô ấy cần thực hiện.

Input

• Mỗi test có nhiều truy vấn. Dòng đầu tiên chứa số lượng truy vấn \(t\) \((1 \le t \le 500)\)
• Dòng đầu tiên của mỗi truy vấn chứa một số nguyên \(n\) \((2 \le n \le 100)\) - số lượng bạn Alice có
• Dòng thứ hai của mõi truy vấn chứa n số nguyên \({a_1}, {a_2},...{a_n}\) \((1 \le {a_i} \le 10^9)\) - vị trí mỗi bạn của cô ấy

Output

• Với mỗi truy vấn, hãy đưa ra số lượng cuộc gọi nhóm tối thiểu mà cô ấy cần thực hiện để tất cả bạn bè của cô ấy đều ở cùng một địa điểm.

Example

4
5
1 2 3 4 5
5
1 1 1 2 2
11
3 1 4 1 5 9 2 6 5 3 5
5
1 2 2 2 2

2
2
5
1