Paprika và Hoán Vị

Cho một mảng gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$. Bạn muốn biến mảng này thành một hoán vị của các số nguyên từ $1$ đến $n$.

Để làm điều đó, bạn có thể thực hiện các thao tác. Trong mỗi thao tác, bạn chọn một chỉ số $i$ ($1\le i\le n$) và một số nguyên $x>0$, rồi gán $a_i:=a_{i}modx$ (thay $a_i$ bằng phần dư của $a_i$ khi chia cho $x$). Ở các thao tác khác nhau, $i$ và $x$ được chọn có thể khác nhau.

Hãy xác định số thao tác ít nhất cần thực hiện để biến mảng thành một hoán vị của các số nguyên từ $1$ đến $n$. Nếu không thể, in ra $-1$.

Một hoán vị là một mảng gồm $n$ số nguyên phân biệt nhận giá trị từ $1$ đến $n$ theo thứ tự bất kỳ. Ví dụ, $[2,3,1,5,4]$ là một hoán vị, nhưng $[1,2,2]$ thì không (số $2$ xuất hiện hai lần) và $[1,3,4]$ cũng không (với $n=3$ nhưng có số $4$).

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ — số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số thao tác ít nhất cần thực hiện để biến mảng thành một hoán vị của $1$ đến $n$, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le {10}^5$
• $1\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ