There is a shop that sells action figures near Monocarp's house. A new set of action figures will be released shortly; this set contains $$$n$$$ figures, the $$$i$$$-th figure costs $$$i$$$ coins and is available for purchase from day $$$i$$$ to day $$$n$$$.

For each of the $$$n$$$ days, Monocarp knows whether he can visit the shop.

Every time Monocarp visits the shop, he can buy any number of action figures which are sold in the shop (of course, he cannot buy an action figure that is not yet available for purchase). If Monocarp buys at least two figures during the same day, he gets a discount equal to the cost of the most expensive figure he buys (in other words, he gets the most expensive of the figures he buys for free).

Monocarp wants to buy exactly one $$$1$$$-st figure, one $$$2$$$-nd figure, ..., one $$$n$$$-th figure from the set. He cannot buy the same figure twice. What is the minimum amount of money he has to spend?

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

the first line contains one integer $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — the number of figures in the set (and the number of days);
the second line contains a string $$$s$$$ ($$$|s| = n$$$, each $$$s_i$$$ is either 0 or 1). If Monocarp can visit the shop on the $$$i$$$-th day, then $$$s_i$$$ is 1; otherwise, $$$s_i$$$ is 0.

Additional constraints on the input:

in each test case, $$$s_n$$$ is 1, so Monocarp is always able to buy all figures during the $$$n$$$-th day;
the sum of $$$n$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, print one integer — the minimum amount of money Monocarp has to spend.

Note

In the first test case, Monocarp buys the $$$1$$$-st figure on the $$$1$$$-st day and spends $$$1$$$ coin.

In the second test case, Monocarp can buy the $$$1$$$-st and the $$$3$$$-rd figure on the $$$3$$$-rd day, the $$$2$$$-nd and the $$$4$$$-th figure on the $$$4$$$-th day, and the $$$5$$$-th and the $$$6$$$-th figure on the $$$6$$$-th day. Then, he will spend $$$1+2+5=8$$$ coins.

In the third test case, Monocarp can buy the $$$2$$$-nd and the $$$3$$$-rd figure on the $$$3$$$-rd day, and all other figures on the $$$7$$$-th day. Then, he will spend $$$1+2+4+5+6 = 18$$$ coins.

Action Figures

Examples