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.
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
For each line of shooting sequence print one integer, the number of enemies killed.
Input | Output |
---|---|
4 2 10 3 011 5 00101 11 00110110001 | 0 1 1 2 |