Hiếu rất thích chuột lang và quyết định sẽ sắp xếp chỗ ở cho chúng tại nhà nhiều nhất có thể trong ~n~ ngày tới. Mỗi ngày, Hiếu sẽ đi mua 1 con hoặc gọi bác sĩ để kiểm tra bọn chúng.

Thật đáng tiếc rằng, cái cửa hàng mà Hiếu biết lại không biết giới tính của các con chuột, Hiếu cũng vậy. Chỉ có mỗi ông bác sĩ là biết phân biệt.

Để giữ các con chuột, tất nhiên Hiếu cần các lồng nhốt. Hiếu cũng lại mua cùng cửa hàng đấy. Lại đáng tiếc cho Hiếu, cái cửa hàng oái oăm lại chỉ bán cái lồng đôi. Không thể có hơn 2 con ở trong đó.

Vì Hiếu lại rất thương các con chuột nên không nỡ lòng nào để 2 con khác giới tính cùng một chuồng. Hãy giúp Hiếu tính số lượng chuồng phải mua trong trường hợp tệ nhất mà vẫn đảm bảo không có hơn 2 con sống trong đó và nếu có 2 con, chúng phải cùng giới. (Ở bài này, chúng ta sẽ coi như có 2 giới tính đực và cái).

Input

• Dòng đầu tiên chứa số lượng test case ~t(1 \leq t \leq 100)~
• Dòng đầu tiên của mỗi test case chứa ~n ( 1 \leq n \leq 10^5)~ - số ngày Hiếu lập kế hoạch
• Dòng thứ hai của mỗi test case chứa ~n~ số ~a_1,a_2,...,a_n (1 \leq a_1, a_2, …, a_n \leq 2)~. Nếu ~a_i = 1~ vào ngày thứ ~i~, Hiếu sẽ mua 1 con chuột. Nếu ~a_i = 2~ vào ngày thứ ~i~, Hiếu sẽ gọi ông bác sĩ đến để kiểm tra giới tính các con chuột Hiếu đang có.

Output

• In ra số chuồng ít nhất phải mua để cho dù giới tính các con chuột như nào, chúng ta vẫn có thể sắp xếp chúng thỏa mãn yêu cầu đề bài

Sample Input

6

3
1 1 1

3
2 2 2

5
1 1 1 2 1

10
1 2 1 2 1 2 1 2 1 2

20
1 2 1 1 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1 1

20
2 1 1 2 1 1 2 1 2 2 1 1 1 2 2 1 1 1 1 2

Sample Output

3
0
3
4
12
9

Note

• Ở test đầu tiên, Hiếu phải đặt mỗi con vào chuồng riêng biệt vì không biết giới tính con nào cả
• Ở test thứ 2, Hiếu không mua con nào thì không phải mua chuồng
• Ở test thứ 3, Hiếu phải mua 3 chuồng riêng cho 3 con cho tới ngày thứ 4. Khi Hiếu biết giới tính chúng rồi, sẽ ít nhất 2 con cùng giới tính bị nhốt vào 1 chuồng, con còn lại ở chuồng khác. Vậy, Hiếu còn thừa 1 chuồng cho con mua vào ngày thứ 5
• Ở test thứ 4, vào ngày đầu tiên, chúng ta phải mua 1 chuồng để nhốt 1 con vào. Sau đó ông bác sĩ sẽ đến kiểm tra. Và tương tự thế đến ngày ông bác sĩ đến lần thứ 3, tức là ngày thứ 6 -> Lúc này, chúng ta có 3 chuồng, 3 con với mô tả tối ưu nhất: 1 chuồng có 2 con, 1 chuồng có 1 con, 1 chuồng không con nào. Khi mua con chuột thứ 4 vào ngày 7, ta cho nó vào chuồng không con nào và đến ngày 8, khi ta biết giới tính con ngày 7, lúc này chúng ta vẫn có 3 chuồng.
• Lúc này số lương con đực có thể là 0,1,2 và không thể là 3 hoặc 4 vì vai trò đực cái như nhau. Giả sử số lượng là 1 thì chúng ta có 3 con cái, 1 đực thì 3 chuồng sẽ mô tả là: 2 con 1 chuồng, 2 con còn lại 2 chuồng riêng biệt, vậy thì khi mua con thứ 4, tổng chuồng là 4.
• Nếu số lượng đực là 0 thì số con cái là 4, xếp vào 2 chuồng, chuồng còn lại không có con nào thì con thứ 5 sẽ ở chuồng đó, tổng chuồng là 3, tuy nhiên cái đáp án này không phù hợp với giải thích số lượng đực là 1 do đề bài yêu cầu cho dù thế nào vẫn phải đảm bảo điều kiện đưa ra nên ta phải bỏ qua giả thuyết này. Tương tự với số lượng đực là 2
• Kết luận, ở test này 4 chuồng là tối ưu nhất