G. Odd Non Primes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Roshan has devised an intriguing card game for his friends Gopal and Vasu. He presents them with a deck of cards, each labeled with an integer, and challenges them to find the maximum value of a special expression based on the cards in any sub-deck. The value of special expression of a sub-deck is determined using the following rule:

  • (Number of odd numbered cards) − (Number of prime numbered cards)

A sub-deck is any contiguous sequence (containing atleast 1 card) of cards drawn from the original deck. Gopal and Vasu must find the sub-deck that maximizes the value of this expression. While Gopal thinks about calculating the value for each possible sub-deck, Vasu suspects there might be a more efficient way to figure it out.

Can you help them determine the highest value of special expression?

Input

Each test contains multiple test cases. The first line contains a single integer t $$$(1 \le t \le 10_{}^3)$$$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer n $$$(1 \le n \le 10_{}^3)$$$  — the number of cards.

The second line of each test case contains n integers $$$a_1 , a_2 , ... , a_n$$$ $$$(1 \le a_i \le 10_{}^6)$$$  — the number of cards of type i, for each $$${1 \le i \le n}$$$ .

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10_{}^3$$$.

Output

For each test case, output a single integer — the maximum possible value of the special expression.

Example
Input
5
6
1 2 3 4 5 6
8
5 7 3 8 3 9 10 1
6
6 3 3 3 5 5
6
5 6 4 1 4 5
9
8 6 4 2 1 3 5 7 9
Output
1
2
0
1
2
Note

In the first testcase, the maximum possible value of the special expression is when we only select the first card.

In the third testcase, the maximum possible value of the special expression is when we select the subdeck starting at third and ending at fourth card.

In the last testcase, the maximum possible value of the special expression is when we select the subdeck starting at fifth and ending at ninth card $$$1,3,5,7,9$$$.