Dr. TC has a new patient called Goblin. He wants to test Goblin's intelligence, but he has gotten bored of his standard test. So, he decided to make it a bit harder.

First, he creates a binary string$$$^{\text{∗}}$$$ $$$s$$$ having $$$n$$$ characters. Then, he creates $$$n$$$ binary strings $$$a_1, a_2, \ldots, a_n$$$. It is known that $$$a_i$$$ is created by first copying $$$s$$$, then flipping the $$$i$$$-th character ($$$\texttt{1}$$$ becomes $$$\texttt{0}$$$ and vice versa). After creating all $$$n$$$ strings, he arranges them into an $$$n \times n$$$ grid $$$g$$$ where $$$g_{i, j} = a_{i_j}$$$.

A set $$$S$$$ of size $$$k$$$ containing distinct integer pairs $$$\{(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)\}$$$ is considered good if:

$$$1 \leq x_i, y_i \leq n$$$ for all $$$1 \leq i \leq k$$$.
$$$g_{x_i, y_i} = \texttt{0}$$$ for all $$$1 \leq i \leq k$$$.
For any two integers $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq k$$$), coordinate $$$(x_i, y_i)$$$ is reachable from coordinate $$$(x_j, y_j)$$$ by traveling through a sequence of adjacent cells (which share a side) that all have a value of $$$\texttt{0}$$$.

Goblin's task is to find the maximum possible size of a good set $$$S$$$. Because Dr. TC is generous, this time he gave him two seconds to find the answer instead of one. Goblin is not known for his honesty, so he has asked you to help him cheat.

$$$^{\text{∗}}$$$A binary string is a string that only consists of characters $$$\texttt{1}$$$ and $$$\texttt{0}$$$.

Input

The first line of the input consists of a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ — the number of test cases.

The first line of each test contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the length of the binary string $$$s$$$.

The second line of each test contains a single binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single number, the maximum possible size of a good set of cells from the grid.

Note

In the first example, the following grid has been written on the board:

$$$$$$ 1 0 0 $$$$$$ $$$$$$ 0 1 0 $$$$$$ $$$$$$ 0 0 1 $$$$$$

The set that consists of cells $$$(1, 2)$$$ and $$$(1, 3)$$$ is good. The set that consists of cells $$$(1, 1)$$$ and $$$(1, 2)$$$ is not good, since the value of cell $$$(1, 1)$$$ is not $$$0$$$. The set of cells $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$ is good and has a maximum size of $$$3$$$. Note that the set of cells $$$(2, 1)$$$, $$$(3, 1)$$$, and $$$(3, 2)$$$ is also good with a maximum size of $$$3$$$.

In the second example, the following grid is written on the board:

$$$$$$ 1 0 1 0 $$$$$$ $$$$$$ 0 1 1 0 $$$$$$ $$$$$$ 0 0 0 0 $$$$$$ $$$$$$ 0 0 1 1 $$$$$$

And the maximum possible size of a good set is $$$9$$$.

Goblin

Examples