Welcome to NTHU Online Judge! You must notice the avenue planted with many streetlamps. Since energy issue is serious, NTHU decided to turn off some streetlamps. However, there are so many activities held in NTHU, sometimes we need more lights for safety, so a fixed setting is not flexible.
As a computer science student, Scott designed a system to control the setting of streetlamps. At first, he gave every streeplamps a number from 1, 2, 3, ..., and so on. There is a control panel with two lines of buttons, and the buttons each line are indexed from 1 to n provided that the total number of streeplamps is n. When Scott pushed a button on first line, e.g: i_th one, the status of i_th streetlamp changes. Changing status means that if a streetlamp is turn off, then it would be turned on, and vice versa. This kind of action is called "normal" push.
Another line of buttons is more powerful, called "toggle" push. If we toggle pushed the i_th button, then the status of streetlamps from the i_th streetlamp to the last(n_th) one would be changed. For example, if we toggle pushed 5th button, then the status of streetlamps with index 5, 6, ..., n will be changed.
Now we want to know how to minimize the total number of normal push and toggle push on buttons. Please write a program to help Scott. We assume that originally all streetlamps are turned off.
The first line is the number of test cases. Each test case starts with an integer n and the next line are n integers v_1, v_2, ..., v_n. n(<=10^6) is the number of streeplamps, and v_i is i_th streeplamp status for final setting. v_i is either 0 or 1, 0 is turned off and 1 is turned on.
For each test case, output the test case number and the minimum number of push. See sample for more details.