Raju and his string

Raju is playing with his string 'S' of length 'N' consisting of lowercase letters only. He wonders if his string is a good string. Print 1 if 'S' is a good string else print 0.

A string is a good string if the parity of the number of unique characters in the string is equal to the parity of its length.

Parity is the property of an integer of whether it is even or odd.

Example :

'N' = 5, 'S' = "abacd".

The number of unique characters in 'S' is 4.

The parity of 4 and parity of 'N'( which is 5) is not the same. So, the string 'S' is not a good string. We will print 0.

Input Format :

The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer 'N', denoting the size of the string 'S'.

The next line contains a string of size 'N'.

Output format :

For each test case, print 1 if the parity of the number of unique characters is same as the parity of size of the string.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5

The string 'S' consists of lowercase letters only.

The Sum of 'N' over all test cases is <= 10 ^ 5.

Time Limit: 1 sec