Eurozwrotnica

브로츠와프 근교의 작은 역에서 일하는 철도원 파벨을 기억하시나요? 최근 몇 달 사이 그의 일에는 큰 변화가 있었습니다. Euro 2012를 앞둔 철도 인프라 확장 공사로, 그의 작은 역에 두 번째 선로가 새로 놓였습니다.

확장 후에도 파벨의 역은 단방향입니다. 열차 편성은 서쪽에서 역으로 들어와 반대쪽인 동쪽으로 빠져나갑니다. 파벨은 들어오는 각 편성을 어느 선로로 보낼지, 그리고 각 편성을 언제 역에서 내보낼지를 결정합니다. 한 선로에는 여러 편성이 대기할 수 있지만, 그 선로에 들어온 순서 그대로 나가야 합니다. 같은 선로 위에서는 편성끼리 서로 추월할 수 없습니다.

이런 구조 덕분에 파벨은 역을 떠나는 편성의 순서를 조절할 수 있습니다. 예를 들어 편성이 C, A, B 순서로 들어온다면, 첫 번째 편성을 1번 선로로 보내고 다음 두 편성을 2번 선로로 보낸 뒤, A, B, C 순서로 내보낼 수 있습니다.

내일 역에는 $1$부터 $N$까지 번호가 매겨진 $N$개의 편성이 들어옵니다. 편성이 도착하는 순서가 주어질 때, 선로를 적절히 배정하여 편성이 $1, 2, \ldots, N$ 순서로 역을 떠나도록 만들 수 있는지 판단하세요.

첫 줄에 테스트 세트의 개수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 각 테스트 세트가 차례로 주어집니다.

각 테스트 세트의 첫 줄에는 역으로 들어오는 편성의 수 $N$ ($1 \le N \le 10^6$)이 주어집니다. 둘째 줄에는 편성이 도착하는 순서대로 서로 다른 정수 $p_i$ ($1 \le p_i \le N$) $N$개가 공백으로 구분되어 주어집니다.

각 테스트 세트마다, 편성을 $1, 2, \ldots, N$ 순서로 내보낼 수 있으면 TAK를, 그렇지 않으면 NIE를 한 줄에 출력하세요.