Java

Given a string S with repeated characters (only lowercase).

The task is to rearrange characters in a string such that no two adjacent characters are same.

Note : It may be assumed that the string has only lowercase English alphabets.

Input:

The first line of input contains an integer T denoting the number of test cases.

Then T test cases follow. Each test case contains a single line containing a string of lowercase English alphabets.

Output:

For each test case in a new line print "1" (without quotes) if the generated string doesn't contains any same adjacent characters,

else if no such string is possible to be made print "0" (without quotes).

Constraints:

1 <= T <= 1001 <= length of string <= 104

Example:

Input:

3geeksforgeeksbbbabaaacdbbbbb

Output:110Exp

Please comment it . Thanks