Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4010
Neighboring Characters

Time Limit: 4 Seconds      Memory Limit: 65536 KB

Given a string \(s\) of length \(n\), let's define the neighbors of the \(i\)-th character (\(1 \le i \le n\)) as follows:

  • If \(1 < i < n\), the neighbors of the \(i\)-th character are the \((i-1)\)-th character and the \((i+1)\)-th character;
  • If \(i = 1\), the neighbors of the 1st character are the 2nd character and the \(n\)-th character;
  • If \(i = n\), the neighbors of the \(n\)-th character are the \((n-1)\)-th character and the 1st character.

A string \(s\) is good, if and only if all the characters in the string are different from their neighbors.

DreamGrid would like to delete \(k\) continuous characters from string \(s\) to form a new string \(\bar{s}_k\). Note that the \(n\)-th character and the 1st character are also continuous (you can consider the string as a ring). Please tell him if it's possible to make \(\bar{s}_k\) a good string for all \(0 \le k < n\).

Input

There are multiple test cases. The first line of the input contains an integer \(T\), indicating the number of test cases. For each test case:

The first and only line contains a string \(s\) (\(1 \le |s| \le 10^6\)) consists of lowercase English letters.

It's guaranteed that the sum of \(|s|\) over all test cases will not exceed \(1.2 \times 10^7\).

Output

For each test case output one line containing one string of length \(|s|\) consists of '0' and '1'. If the \(i\)-th (the index starts from 1) character is '1', it is possible to make \(\bar{s}_{i-1}\) a good string; If its '0', it is impossible to make \(\bar{s}_{i-1}\) a good string.

Sample Input

5
abab
aabbaa
abcabc
abcdef
a

Sample Output

1011
000011
110111
111111
1

Hint

For the first sample test case:

  • When \(k = 0\), string "abab" is good;
  • When \(k = 2\), string "ab" is good;
  • When \(k = 3\), string "a" is good.


Author: CHEN, Jingbang
Source: ZOJ Monthly, March 2018
Submit    Status