포뮬러 원

꼬마 바이티는 매년 바이트타운과 바이트버그를 잇는 트랙에서 열리는 포뮬러 원 경주를 즐겨 봅니다. 그가 가장 좋아하는 순간은 추월이며, 되도록 많은 추월을 보고 싶어 합니다.

바이티는 $n$대의 자동차가 참가하는 경주를 상상합니다. 출발 위치가 $i$번인 자동차(각 $1 \le i \le n$)는 경주 동안 정확히 $a_i$번 추월을 합니다. 편의상 어느 순간에도 추월은 최대 한 번만 일어나며, 그 추월에는 정확히 두 대의 자동차만 관여한다고(한 대가 다른 한 대를 앞지른다고) 가정합니다.

이러한 경주가 과연 가능한지 바이티가 판단할 수 있도록 도와주세요.

첫 번째 줄에 테스트 케이스의 수 $t$가 주어집니다.

각 테스트 케이스는 두 줄로 이루어집니다. 첫 번째 줄에는 경주에 참가하는 자동차의 수 $n$ ($1 \le n \le 1\,000\,000$)이 주어집니다. 두 번째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)이 주어지며, $a_i$는 출발 위치가 $i$번인 자동차가 한 추월의 횟수입니다.

하나의 입력 파일 전체 크기는 20 MB를 넘지 않습니다.

각 테스트 케이스마다 한 줄을 출력합니다. 설명된 경주가 가능하면 TAK(폴란드어로 "예")을, 불가능하면 NIE(폴란드어로 "아니오")를 출력합니다.