DNA 분자는 문자의 연속으로 나타낼 수 있으며, 각 글자는 {'A','C','G','T'} 중 하나이다. 즉, 'A', 'ATG', 'GTA'는 모두 서로 다른 DNA 분자를 나타낸다.

은기는 DNA 분자를 연구하는 화학자이고, DNA 분자를 다음과 같이 고칠 수 있다.

• A ↔ TC (A는 TC로 변할 수 있고, 그 역으로 변할 수도 있다)
• C ↔ AG
• G ↔ CT
• T ↔ GA

은기는 한 DNA 분자를 적절히 고쳐 다른 DNA 분자를 만들려고 한다. 예를 들면, AA → TCA → TAGA → TAT 이다.

은기의 연구실에는 DNA 분자가 N개 있다. 이때, 가능한 모든 쌍에 대해서, 첫 번째 분자를 두 번째 분자로 고칠 수 있는지 없는지 알아내는 프로그램을 작성하시오.

입력 형식

첫째 줄에 DNA 분자의 수 N (2 ≤ N ≤ 100)이 주어진다. 분자는 입력으로 주어진 순서대로 1번부터 N번이다.

다음 N개 줄에는 DNA 분자가 한 줄에 하나씩 주어진다. 분자는 'A', 'C', 'G', 'T'로만 이루어져 있고, 길이는 50,000을 넘지 않는다.

출력 형식

각 줄마다 N개의 문자를 N줄에 걸쳐서 출력한다. i번째 줄의 j번째 글자가 '1'인 경우에는 i번째 분자를 j번째 분자로 고칠 수 있다는 뜻이며, '0'인 경우에는 고칠 수 없다는 뜻이다.

예제 입력 1

4
AA
TAT
C
CGTAC

예제 출력 1

1100
1100
0011
0011

예제 입력 2

4
A
C
G
T

예제 출력 2

1000
0100
0010
0001

예제 입력 3

4
AAA
CCC
TATA
CACA

예제 출력 3

1111
1111
1111
1111