"Do you know, why I use a knife? Guns are too quick. You can't savour all the little emotions. You see, in their last moments, people show you who they really are. So in a way, I know your friends better than you ever did. Would you like to know which of them were cowards?"

Joker has both knives and guns, and he wants to replace the guns with other knives. Given a list of guns and knives where knives are denoted by '1' and guns are denoted by '0' find how many knives can joker have after exactly one move to obtain the maximum number of knives. The only one move is explained as: Joker selects a segment and changes all guns in that segment with knives and all knives in that segment with guns. An empty segment cannot be selected.

Input

The first line contains the number of test cases T (1 <= T <= 21000). Each test case is followed by 2 lines:

1. n (1 <= n <= 100) Number of knives and guns Joker has.
2. String of 0 and 1 separated by spaces in between to denote guns and knives respectively.

Output

Maximum number of knives Joker can have after exactly one move.

Example

Input:
3
4
1 0 0 1
3
1 1 1
5
1 0 0 0 0

Output:
4
2
5

Explanation

Test Case 1 : Joker flips segment shown inside brackets 1 (0 0) 1 to get 1 1 1 1. Hence, he has 4 knives finally.

Test Case 2 : Joker flips segment shown inside brackets 1 1 (1) to get 1 1 0. Hence, he has 2 knives finally.

Test Case 3 : Joker flips segment shown inside brackets 1 (0 0 0 0) to get 1 1 1 1 1. Hence, he has 5 knives finally.