Tại một trường đua trong đó có \(N\) cuộc đua ngựa khác nhau được diễn ra trong một ngày. Biết cuộc đua thứ \(i\) là con ngựa có số hiệu \(a_i\) thắng. John sở hữu \(M\) con ngựa được đánh số từ 1 đến \(M\). John chỉ quan tâm đến thành tích của tất cả những con ngựa được đánh số từ 1 đến M và số lần mà con ngựa thứ \(j (1≤j≤M)\) thắng. John có \(X\) tấm thẻ thần kì, một tấm thẻ thần kì được phép thay đổi con ngựa về đích của 1 trận đua, cụ thể, khi John sử dụng 1 tấm thẻ thần kì, John chọn thay đổi con ngựa thắng ở cuộc đua thứ \(i\) với ban đầu con ngựa \(a_i\) thắng thành con \(a_j\) thắng.

Yêu cầu: Hãy giúp John chỉ được sử dụng tối đa X tấm thẻ thần kì để số lần con ngựa thắng ít nhất trong M con ngựa của John là lớn nhất.

Input

• Dòng 1 chứa số nguyên \(T(1≤T≤10)\) – là số bộ test, với mỗi bộ test gồm:

• Dòng 1: chứa 3 số nguyên \(N, M, X (1 ≤ M ≤ N ≤ 10^5, X ≤ 10^5\)).

• Dòng 2: Chứa \(N\) số nguyên \(a_1,a_2,…,a_n\),với \(a_i ≤ N\), biểu thị con ngựa thắng ở cuộc đua thứ \(i\) có số hiệu là \(a_i\).

Output:

In ra \(T\) dòng, mỗi dòng tương ứng là số lần con ngựa thắng ít nhất trong \(M\) con ngựa của John là lớn nhất với test tương ứng.

Sample Input

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

Sample Output

3
1
2