Welcome to Lululand! Making friendship is a bit different here. There are some rules in making friendship. Here, one person can make only 2 friends and a group of friends can be formed consisting of exactly 3 person. Members of a group are only friends to each other in the same group, they cannot make friendship to any person who is not in the same group. Again, every person in the lululand has a unique ID number. A group can be formed if the summation of 3 members ID number is Even. There is an administrator in the Lululand, who decides how the groups will be formed. President of the Lululand, Mr. Lulu assigned you as the administrator of the Lululand. Your task is to determine how many persons will have no friends if you form groups optimally?
Input
The first line of the input contains a single integer t (1 ≤ t ≤ 10) — the number of test cases. Each case starts with an integer n (1 ≤ n ≤10000) which indicates the number of people in Lululand. The next line will contain n integers, ID card numbers of the people, (0 ≤ ID number ≤ 100000000).
Output
For each case, print the case number and the amount of minimum number of people who will have no friends after forming groups. See the samples for exact formatting.
Sample
| Input | Output |
|---|---|
1 4 0 9 1 2 | Case 1: 1 |
Explanation of the sample test case.
Here you can form a group with the ID numbers of 0,9,1 as the sum of them is 0+9+1=10 which is even, so only one person whose id number is 2 has no friends, so the output is 1.
