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\).

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\).

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.

提交代码