Oishi Teacher and Her Naughty Class

Oishi teacher has returned to her class after the tiffin break. She noticed that some students who returned to the class did not sit according to the rule she had implemented to keep the class quiet.

The class has a total of N students, and they sit in one row. Each student has a unique id from 1 to N. Oishi teacher noticed that any two students who have prime ids do not talk much and listen to Oishi teacher’s lecture and follow the class rules. Same thing happens when any two students with non-prime ids sit together. But if two students sit who belong to different types of ids(one prime and one non-prime id), they always make noise and are generally less attentive to the lecture.

So she decided to organize the seat plan in such a way that she can keep the class quiet and deliver the lectures well. After the tiffin break, some students have already returned to class before her and took some seats. So it is not possible to rearrange all the students. But the students who will come after her arrival can be placed into empty seats. For that, she has made a system to motivate herself. That is, if two students with different parities (one student with prime id and one student with non-prime id) sit together and make noise, she counts it as a quarrel and eats one chocolate for each quarrel. As Oishi teacher is on diet, she does not want to eat many chocolates, So, those students who come after her arrival, should sit in such a way that the total number of quarrels will be minimal.

Help Oishi teacher to make the seat plan in a way so that she can minimize her chocolate consumption.

Input

There will be T (1 ≤ T ≤ 10) test cases.

For each test case, there will be a single integer n (1 ≤ n ≤ 10000), the number of students in class.

Then for each n, there will be n ids: a1, a2, a3, ..., an. Each positive id will be unique and will range from 1 to N. If there is a ‘0’ it means the seat is empty and Oishi teacher will assign the seat to the students who came after her arrival.

Output

Output a number: the minimum number of chocolates Oishi teacher will have to eat.

Sample

Input	Output
3 1 0 1 1 2 1 2	0 0 1