5.1 ⚖️🔢 Parity Unification: Even and Odd Harmony 🔄💡

Score: 15pts

Time Limit: 5.00 sec

In a realm where numbers are split between two factions—those with even parity and those with odd parity—a quest for unity begins! Your task is to bring harmony by making all the numbers in an array a of n positive integers share the same parity.

You have a special power: whenever you find two numbers with different parity (one even, one odd), you can combine their strengths by replacing the smaller number with the sum of the two. Your mission is to figure out the minimum number of operations needed to make all elements in the array have the same parity.

You have a special power: whenever you find two numbers with different parity (one even, one odd), you can combine their strengths by replacing the smaller number with the sum of the two. Your mission is to figure out the minimum number of operations needed to make all elements in the array have the same parity.

Constraints

t(1≤t≤10^4)

n(1≤n≤2*10^5)

n(1≤n≤2*10^5)

Input Format

The first line contains a single integer t — the number of test cases.

The first line of each test case contains a single integer n

The second line contains n integers a1,a2,a3….an - the elements of array a

The first line of each test case contains a single integer n

The second line contains n integers a1,a2,a3….an - the elements of array a

Output Format

For each test case, output a single integer — the minimum number of operations required.

Example 1

Input:

7

5

1 3 5 7 9

4

4 4 4 4

3

2 3 4

4

3 2 2 8

6

4 3 6 1 2 1

6

3 6 1 2 1 2

5

999999996 999999997 999999998 999999999 1000000000

Output:

0

0

2

4

3

3

3

Explanation:

Example is self explanatory

7

5

1 3 5 7 9

4

4 4 4 4

3

2 3 4

4

3 2 2 8

6

4 3 6 1 2 1

6

3 6 1 2 1 2

5

999999996 999999997 999999998 999999999 1000000000

Output:

0

0

2

4

3

3

3

Explanation:

Example is self explanatory