A. Short Query
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a$$$ containing $$$n$$$ elements.

You can do the following operation on array $$$a$$$ :

  1. Choose two integers $$$a_{i}$$$, $$$a_{j}$$$ $$$(i ≠ j)$$$.
  2. If $$$(a_{i} + a_{j})$$$ is even, then remove $$$a_{i}$$$, $$$a_{j}$$$ from $$$a$$$ and add $$$(a_{i} + a_{j})$$$ at the end of $$$a$$$.

What are the minimum number of elements in $$$a$$$ after performing the above operation for at most $$$k$$$ times.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first line of test case contains two integers $$$n,k$$$ ($$$1 \le n,k \le 10^3$$$) — the length of the array $$$a$$$ and the number of operations performed.

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^3$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^3$$$.

Output

For each test case, print single integer — minimum number of elements in $$$a$$$ after performing the operation for at most $$$k$$$ times.

Example
Input
8
1 1
1
1 3
5
2 5
4 6
3 1
1 2 3
5 4
3 5 7 9 10
5 3
1 2 3 4 5
7 20
190 910 999 189 672 111 673
10 2
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
Output
1
1
1
2
1
2
1
8
Note

In the $$$5^{th}$$$ test case,

Initially, $$$a$$$ is $$$(3, 5, 7, 9, 10)$$$.

  1. After performing $$$1^{st}$$$ operation $$$a$$$ will be $$$(7, 9, 10, 8)$$$.
  2. After performing $$$2^{nd}$$$ operation $$$a$$$ will be $$$(10, 8, 16)$$$.
  3. After performing $$$3^{rd}$$$ operation $$$a$$$ will be $$$(16, 18)$$$.
  4. After performing $$$4^{th}$$$ operation $$$a$$$ will be $$$(34)$$$.

Hence, total $$$1$$$ element is there in $$$a$$$ after performing $$$4$$$ operations.