Shiku Gets Lucky

One day while playing, Shiku found a sequence of lowercase English letters. Shiku thought it might be an ancient sequence and he could become rich by selling it. He knows that for the sequence to be ancient, there must be a character that occurs more than the half times the length of sequence. But as Shiku is useless, he failed to do even this simple task. So, he asks for your help now. As you are his good friend (?), now you have to determine if it's his lucky day.

More formally, you are given a string s of length n (n is even). For the given string check, if any character has frequency greater than half of n.

We define frequency as the number of time a character occurs in the given string.
The string consists of lowercase English letters only.

Input

The input consists of multiple test cases. The description of the test cases follows.
The first line contains a single integer t (1≤ t ≤100) — the number of test cases.
The first line of each test case consists of one integer n (2 ≤ n ≤ 100000) — The length of the string.
It is guaranteed that n is even.
The second line of each test case contains a string s of lowercase English letters.
Sum of n over all test cases doesn't exceed 100000.

Output

For each test case, Print 1 if any such character exists. Otherwise, print 0.

Sample

Input	Output
4 2 aa 4 abab 6 abcdef 6 abacaa	1 0 0 1