Given an array A of N integers and an integer K. You can perform the following operation any number of times on the given array :

• Choose an integer x such that $1 \le x \le K$
• Choose any index i such that $1 \le i \le N$
• Update A[i] = x

In different operations, different value of x and i can be chosen.

Task

Your task is to count minimum number of operations required such that following conditions are met:

• All elements in array A becomes pairwise distinct.
• Count of array elements with odd value is equal to count of array elements with even value.

If the above conditions cannot be met after any number of operations, return -1.

Note:

• Assume 1 Based Indexing is followed.
• Array A is said to have pairwise distinct elements if and only if the value of all the elements in array A is distinct.

Example 

Assumptions:

• N = 4
• A = [1, 4, 4, 1]
• K = 5

Approach:

• Initial array A is [1, 4, 4, 1]
• Update A[2] = 2, choose x = 2, i = 2.
• Update A[4] = 5, choose x = 5, i = 4.
• Updated array A is [1, 2, 4, 5]
• Now, array A have all distinct elements and count of array elements with odd value is equal to count of array elements with even value.
• Therefore, minimum 2 operations are required.

Note, there can be other possible selections of x and i, at each step but the minimum number of operations remains the same. 

Function description 

Complete the minUpdates function provided in the editor. This function takes the following 3 parameters and returns an integer.

• N: Represents the number of elements in array A
• A: Represents the elements of array A.
• K: Represents the value of K

Input Format 

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains a single integer T, which denotes the number of test cases. T also specifies the number of times you have to run the minUpdates function on a different set of inputs.
• For each test case:-
  • First line contains an integer N.
  • Next line contains N space-separated integers denoting the elements of array A.
  • Next line contains an integer K.

Output Format 

For each test case in a new line, print an integer denoting the minimum number of operations required or print -1, if the conditions cannot be met.

Constraints 

$1 \le T \le 10^2 \\ 1 \le N \le 10^5 \\ 1 \le A[i], K \le 10^9 \\ \text{Sum of N over all test cases doesn't exceed} \ 10^6$

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.