Limits 1s, 512 MB

As we know Mr. Bean is mainly an action movie star. But during this pandemic, he is not able to do any action. So instead of being bored at home, he is playing a video game.

In this game, there is an infinite number of enemies in a line. Mr.Bean will shoot towards the enemies. He will kill the enemies one by one, which means he can’t kill the 2nd enemy before killing 1st and so on. To kill one enemy he has to weaken him first and then kill.

He has two guns one is a weakening gun and another is a killing gun. The bullets of a weakening gun are defined by ‘0’ and the bullets of a killing gun is defined by ‘1’. There is a special characteristic of the weakening bullets which is if a bullet hits an already weakened enemy it will make him stronger again.

You will be given the information about his shooting sequences, for each sequence you have to tell how many enemies he will kill.

Input

The first line contains one integer T, the number of test cases.

Each test case contains an integer N, the number of bullets shot, and string S consisting of ‘0’ and ‘1’ describing the shooting sequence.

T<=10

N<=100000

Output

For each line of shooting sequence print one integer, the number of enemies killed.

Sample

InputOutput
4
2
10
3
011
5
00101
11
00110110001
0
1
1
2

Submit

Login to submit.

Statistics

91% Solution Ratio
masudursouravEarliest, Jul '20
masudursouravFastest, 0.0s
Albertevan2Lightest, 0 B
Nusab19Shortest, 67B
Toph uses cookies. By continuing you agree to our Cookie Policy.