Migrated from Lutece 608 Bandwidth

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Study in BUPT, you cannot get rid of the word bandwidth. Nearly all the courses like "Signal and System", "Digital Signal Processing", "Communication Theory" are related to the bandwidth.

In the night before the exam of Signal and System, you got an incredible filter. In the frequency spectrum, if the maximal amplitude is $X$, then those frequency amplitude is less than $\frac{X}{2}$ would be filtered.

Now your task is to simulate the incredible filter and figure out the bandwidth after being filtered.

Input

First line contains an integer $T$ ($0 < T \leq 10$), indicate there are $T$ cases.

For each case, the first line contains an integer $N$ ($0 < N < 1000$), indicate the bandwidth of the frequency spectrum before being filtered.

Then comes $N$ lines, only formed by - whose length indicate the frequency amplitude (maximal length is not greater than $1000$).

It guaranteed the maximal length in every case will greater than zero.

Output

One line per case.

Each line contains only an integer indicate the bandwidth of the frequency spectrum after being filtered.

Samples

2
6
-
--
----
-
--
-
10
--
--
--
---
-----
------
-----
----
--
-

4
5

Resources

6th BUPT Programming Contest Final