크기가 $n \times n$인 보드가 주어지며, $n^2$개의 각 칸에는 $-1$, $0$, 또는 $1$ 중 하나의 수가 적혀 있습니다. 또한 네 정수 $A_L, A_D, A_R$과 $A_U$가 주어집니다. 우리는 두 개의 꺾은선을 그리려고 합니다:

• 하나는 보드의 왼쪽 위 모서리와 오른쪽 아래 모서리를 연결하며, 칸의 테두리를 따라 오른쪽과 아래쪽으로만 이동합니다.
• 다른 하나는 보드의 왼쪽 아래 모서리와 오른쪽 위 모서리를 연결하며, 오른쪽과 위쪽으로만 이동합니다.

두 꺾은선은 보드를 왼쪽, 아래쪽, 오른쪽, 위쪽의 네 영역(비어 있을 수도 있음)으로 나눕니다. 이 네 영역에 속한 칸들의 합이 각각 $A_L, A_D, A_R$, $A_U$가 되도록 하는 두 꺾은선이 존재하는지 확인하세요. $t$개의 독립적인 테스트 케이스 각각에 대해 TAK (예) 또는 NIE (아니오)를 출력합니다.

그림은 예제 테스트에 나오는 동일한 $5 \times 5$ 보드를 보여줍니다.

왼쪽 그림은 합이 $(1, 0, -2, 1)$ ($A_L, A_D, A_R, A_U$ 순서)인 영역들로의 분할을 보여줍니다. 첫 번째 꺾은선은 단어 RDDDRRDRDR로, 두 번째 꺾은선은 RURUURRUUR로 설명할 수 있습니다(여기서 D, U, R은 각각 테두리를 따라 아래쪽, 위쪽, 오른쪽으로 이동함을 나타냅니다). 예를 들어, 오른쪽 영역은 8개의 칸을 포함하며 그 합은 $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$입니다.

오른쪽 그림은 합이 $(0, 2, -3, 1)$인 영역들로의 분할을 보여줍니다. 왼쪽 영역은 비어 있으므로 그 칸들의 합은 0입니다. 이 꺾은선들은 단어 DRRRRDDRDD와 UUUURURRRR로 설명할 수 있습니다.

같은 보드를 합이 $(-2, 0, 1, 1)$, 즉 $A_L = -2, A_D = 0, A_R = 1, A_U = 1$인 영역들로 분할할 수는 없습니다. 왼쪽 그림에 같은 값들이 다른 순서로 나타난다는 점에 유의하세요 – 순서가 중요합니다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 100\,000$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 보드의 한 변의 길이와 네 영역의 목표 합을 나타내는 다섯 개의 정수 $n, A_L, A_D, A_R, A_U$ ($1 \le n \le 2000; -n^2 \le A_L, A_D, A_R, A_U \le n^2$)가 주어집니다.

테스트 케이스의 다음 $n$개의 줄은 각각 보드를 설명하며, $i$번째 줄에는 $i$번째 행을 설명하는 $n$개의 정수 $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$)이 주어집니다. 보드 전체의 합은 $A_L + A_D + A_R + A_U$와 같습니다.

모든 테스트 케이스에 걸쳐 $n^2$의 총합은 $4\,000\,000$을 초과하지 않습니다.

출력

정확히 $t$개의 줄을 출력합니다 – 각 테스트 케이스마다 보드를 지정된 합을 가진 영역들로 나누는 꺾은선이 존재하면 단어 TAK (예)을, 그렇지 않으면 단어 NIE (아니오)를 출력합니다.

예제

입력

5
5 1 0 -2 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 0 2 -3 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 -2 0 1 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
2 1 -1 0 1
1 0
-1 1
1 0 0 0 0
0

출력

TAK
TAK
NIE
NIE
TAK

노트

처음 세 개의 테스트 케이스는 지문에 제시된 예시들에 해당합니다. 이들은 동일한 보드를 포함하며 순서대로 합 $(A_L, A_D, A_R, A_U)$에 대해 질문합니다:

1. $(1, 0, -2, 1)$, 정답 TAK
2. $(0, 2, -3, 1)$, 정답 TAK
3. $(-2, 0, 1, 1)$, 정답 NIE