GTA

문제

Dubravka the chemist examines DNA molecules in her laboratory. Each DNA molecule is represented with a series of characters, where each characters is from the set {‘A’, ‘C’, ‘G’, ‘T’}. Therefore, ‘A’, ‘ATG’ and ‘GTA’ are series of characters which represent different DNA molecules.

Dubravka can perform the following mutations (alterations) in any part of the DNA molecule:

• A ↔ TC (therefore, the character ‘A’ can be replaced with‘TC’ and vice versa)
• C ↔ AG
• G ↔ CT
• T ↔ GA

Dubravka tends to take a certain molecule and alter it by successively applying these mutations. This results in a different molecule, for example:

AA → TCA → TAGA → TAT.

Dubravka currently has N molecules in her laboratory. Write a programme that will, for each pair of given molecules, determine whether it is possible to end up with the second molecule when starting from the first molecule by applying the mentioned mutations.

입력

The first line of input contains the integer N (2 ≤ N ≤ 100), the number of molecules. The molecules are marked with numbers from 1 to N.

Each of the following N lines contains molecules – series of characters where each character is an uppercase letter ‘A’, ‘C’, ‘G’ or ‘T’. Each series of characters consists of at least one and at most 50 000 characters.

출력

Output exactly N characters in each of N lines. The j-th character in the i-th line should be ‘1’ if it’s possible to get molecule j from the molecule i, otherwise it should be ‘0’. You mustn’t print spaces between individual characters in the same line.

4
AA
TAT
C
CGTAC

1100
1100
0011
0011

4
A
C
G
T

1000
0100
0010
0001

4
AAA
CCC
TATA
CACA

1111
1111
1111
1111