Marbles

Byteted and Bited started a game with marbles. An urn holds an even number of marbles, and every marble carries exactly one digit.

The rules are simple. The two of them take turns drawing one marble each at random from the urn, and the game ends when the urn is empty. The player whose own marbles have the larger product of digits wins. Since they draw one marble at a time in turns, each of them ends up with exactly half of the marbles, and the game is drawn when the two products are equal.

Both boys are ambitious and a draw pleases neither of them. Given the marbles the urn starts with, write a program that decides whether the game can end in a draw.

The first line contains one integer $t$ ($1 \le t \le 1000$), the number of test cases.

Each of the next $t$ lines contains ten non-negative integers $k_0, k_1, \dots, k_9$ ($0 \le k_i \le 10^{15}$), where $k_i$ is the number of marbles marked with the digit $i$. In every test case the sum of the $k_i$ is even and positive.

Print $t$ lines, one per test case, in the order of the input. Print TAK if the game can end in a draw and NIE otherwise. TAK is Polish for yes and NIE is Polish for no.