Khử Số

Cho một dãy số gồm $n$ số nguyên dương $a_1, a_2, ..., a_n$.

Trong một phép biến đổi, bạn thực hiện quy trình sau:

• Chọn một số nguyên $x$ bất kỳ.
• Với mọi vị trí $i$ thỏa mãn $a_i = x$, gán $a_i := 0$.

Hãy tìm số phép biến đổi tối thiểu cần thực hiện để sắp xếp dãy số theo thứ tự không giảm, tức là thỏa mãn $a_1 ≤ a_2 ≤ ... ≤ a_n$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ ($1 ≤ t ≤ 10^4$) là số lượng bộ test. Tiếp theo là mô tả của các bộ test.

Dòng đầu tiên của mỗi bộ test chứa một số nguyên $n$ ($1 ≤ n ≤ 10^5$) là số lượng phần tử của dãy số.

Dòng thứ hai của mỗi bộ test chứa $n$ số nguyên dương $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ n$).

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ test không vượt quá $10^5$ ($\sum n ≤ 10^5$).

Kết quả

Với mỗi bộ test, in ra một số nguyên là số phép biến đổi tối thiểu cần thực hiện để sắp xếp dãy số theo thứ tự không giảm.

Chấm điểm

Subtask 1 (30 points). $\sum n ≤ 2000$

Subtask 2 (70 points). $1 ≤ t ≤ 10^4$; $1 ≤ n ≤ 10^5$; $\sum n ≤ 10^5$

Ví dụ

Input

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

Output

1
2
4
3
0

Ghi chú

Trong bộ test thứ nhất, bạn có thể chọn $x = 3$ cho phép biến đổi, dãy số thu được là $[0, 0, 2]$.

Trong bộ test thứ hai, bạn có thể chọn $x = 1$ cho phép biến đổi thứ nhất và $x = 3$ cho phép biến đổi thứ hai, dãy số thu được là $[0, 0, 0, 0]$.