Zbyszek

헥토르의 친구 Zbyszek는 종이에 점 $N$개를 찍은 뒤, 그 점들을 몇 개의 선분으로 이었습니다. 각 선분은 서로 다른 두 점을 연결하며, 선분끼리는 서로 교차하지 않았습니다. 또한 Zbyszek는 임의의 두 점 사이를 그려진 선분을 따라 이동하는 방법이 최대 한 가지가 되도록 신경 썼습니다. 즉, 이 그림은 사이클이 없는 숲(forest) 구조입니다.

안타깝게도 Zbyszek는 수업 시간에 이 그림을 그리고 있었고, 화가 난 선생님이 종이를 가져가 버렸습니다. Zbyszek는 각 점이 다른 몇 개의 점과 연결되어 있었는지(그 점의 차수)만 기억합니다. 기억하는 이 숫자들이 실제로 위 조건을 만족하는 그림을 나타낼 수 있는지 판별해 주세요.

첫 번째 줄에 테스트 집합의 개수 $Z$가 주어집니다 ($1 \le Z \le 10$).

이어서 각 테스트 집합이 두 줄에 걸쳐 주어집니다. 각 집합의 첫 줄에는 Zbyszek가 찍은 점의 개수 $N$이 주어집니다 ($1 \le N \le 100{,}000$). 둘째 줄에는 정수 $N$개 $X_1, X_2, \dots, X_N$이 주어지며, $X_i$는 $i$번째 점이 연결되어 있던 점의 개수(그 점의 차수)입니다 ($1 \le X_i \le 100{,}000$).

각 테스트 집합마다 한 줄에 답을 출력합니다. 기억한 숫자들이 조건을 만족하는 그림(주어진 차수를 그대로 갖는 숲)을 하나라도 만들 수 있으면 TAK을, 그럴 수 없으면 NIE를 출력합니다.

원래 문제는 가능한 그림을 하나 복원해서 출력하도록 요구했지만, 같은 숫자들에 들어맞는 그림이 여러 개일 수 있어 그 출력은 유일하지 않습니다. 이 버전에서는 그러한 그림이 존재하는지 여부만 묻고, 그 답은 항상 유일합니다.