Busy Beaver는 $N$ ($2 \le N \le 500$)개의 정점이 $1$부터 $N$까지 번호 매겨진 무방향, 연결, 가중치 없는 그래프를 가지고 놀고 있었습니다. 그는 모든 정점 쌍 $1 \le i < j \le N$에 대하여 정점 $i$에서 정점 $j$까지의 최단 경로 길이 $A_{i,j}$를 메모지에 적었습니다. 이 숫자들을 모두 적는 것이 메모지 공간을 너무 많이 차지한다는 것을 깨달은 Busy Beaver는 $A_{i,j}$를 $5$로 나눈 나머지인 $B_{i,j}$만을 메모지에 적기로 했습니다.

이제 Busy Beaver는 그래프를 잃어버렸고, $B_{i,j}$ 값들만 적힌 메모지만 가지고 있습니다. Busy Beaver가 가능한 그래프를 재구성하도록 돕거나, 그러한 그래프가 존재하지 않아 그가 실수했음을 판별해 주세요.

형식적으로, $N$과 $0 \le B_{i,j} < 5$인 $B_{i,j}$가 주어졌을 때, 정점 $i$와 $j$ 사이의 최단 경로 길이가 $B_{i,j} \pmod 5$와 합동인 $N$개의 정점을 가진 무방향, 연결, 가중치 없는 그래프가 존재하는지 결정하세요. 만약 그러한 그래프가 존재한다면, 가능한 그래프 중 하나를 출력하세요.

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수인 정수 $t$ ($1 \le t \le 100$)가 주어집니다. 그 뒤로 각 테스트 케이스에 대한 설명이 이어집니다.

각 테스트 케이스의 첫 번째 줄에는 양의 정수 $N$이 주어집니다.

그다음 $N - 1$개의 줄이 이어집니다. 이 중 $i$번째 줄에는 $N - i$개의 공백으로 구분된 양의 정수가 포함됩니다. $i$번째 줄의 $j$번째 정수는 $B_{i,j+i}$를 나타냅니다.

모든 테스트 케이스에 대한 $N$의 합은 $500$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스에 대하여, 가능한 그래프가 존재하면 "YES"를, 존재하지 않으면 "NO"를 출력하세요. 대소문자는 구분하지 않습니다. 예를 들어, "yEs", "yes", "Yes", "YES" 모두 긍정적인 응답으로 인식됩니다.

프로그램이 "YES"라고 답한다면, 추가로 $N - 1$개의 줄을 출력하세요. 이 중 $i$번째 줄에는 $N - i$개의 정수가 포함되어야 합니다. $i$번째 줄의 $j$번째 정수는 정점 $i$와 정점 $i + j$ 사이에 간선이 있어야 하면 $1$, 없어야 하면 $0$을 출력합니다.

채점

"YES"/"NO" 응답이 올바르지만 제공된 그래프가 틀린 경우, 해당 테스트 케이스 점수의 25%를 받게 됩니다. "YES"라고 답한 각 테스트 케이스에 대하여, 부분 점수를 받으려면 $i$번째 줄에 $N - i$개의 정수($0$ 또는 $1$)가 포함된 정확히 $N - 1$개의 줄을 출력해야 합니다.

• (20점): 모든 테스트 케이스에 대한 $N$의 합은 $10$을 넘지 않습니다.
• (80점): 추가 제약 조건 없음.

예제

입력 1

3
3
1 1
1
3
2 1
1
3
0 0
0

출력 1

YES
1 1
1
YES
0 1
1
NO

참고

첫 번째 테스트 케이스에서, 정점은 3개이며 임의의 두 정점 사이의 최단 거리는 $1 \pmod 5$입니다. 이는 3개의 정점을 가지고 모든 정점 쌍 사이에 간선을 연결한 그래프를 구성하여 달성할 수 있습니다.

두 번째 테스트 케이스에서, 정점은 3개이며 정점 1과 2 사이의 최단 거리는 $2 \pmod 5$이고, 정점 1과 3 사이 및 정점 2와 3 사이의 최단 거리는 모두 $1 \pmod 5$입니다. 이는 3개의 정점을 가지고 정점 1과 3 사이, 그리고 정점 2와 3 사이에 간선을 연결한 그래프를 구성하여 달성할 수 있습니다.

세 번째 테스트 케이스에서, 정점은 3개이며 임의의 두 정점 사이의 최단 거리는 $0 \pmod 5$입니다. 가중치 없는, 무방향, 연결 그래프 중 이 테스트 케이스를 만족하는 그래프는 존재하지 않음을 보일 수 있습니다.