Three-bit Computers Strike Back

After the Three-bit Computers (KTB) turned out to be an enormous flop, the scientists of Byteland have a wonderful new idea: Quantum Three-bit Computers (KKTB). The KTB machines are now regarded as a mere warm-up before the real challenge, the KKTB.

The new quantum computers are expected to have unprecedented power, and so on and so on, plenty of fiddly olympiad problems, and so on and so on. Let us get to the point.

As before, the fundamental difficulty is initializing the memory. With quantum computers, however, the trouble is of a completely different kind. Every operation performed on a KKTB element has side effects, that is, it influences other elements of the computer. Cancelling out these side effects is very expensive, so initializing the memory bit by bit is impossible. There is another approach, though: controlled medium-range pulses (SISZ). The scientists can generate pulses whose effect on each memory bit of the KKTB can be computed exactly. These pulses can be emitted very quickly, so using even a large number of them is cheaper than initializing the memory bit by bit. The question is whether the whole memory can be zeroed using only SISZ. Your task is to write a program that answers this question.

More formally, each memory bit can be in one of $n$ states numbered $0, \dots, n-1$. A SISZ pulse acts on all bits in the same way, so it can be treated as a function $f : \{0, \dots, n-1\} \to \{0, \dots, n-1\}$. For example, $f(3) = 5$ means that after the pulse $f$ is emitted, every bit that was in state $3$ moves to state $5$. The scientists can emit pulses $f_1, \dots, f_k$. Your task is to decide whether there is a sequence of pulses that brings every bit to state $0$ (zeroes it), no matter its initial state.

Task

Write a program that:

• reads the description of the available pulses,
• checks whether the memory can be zeroed,
• writes the answer to standard output.

Each test consists of several data sets. The first line of standard input contains a single natural number $T$ ($1 \le T \le 10$), the number of data sets. The data sets follow.

Each data set starts with a line containing two natural numbers $n$, $k$ ($1 \le n \le 200$, $1 \le k \le 5$), where $n$ is the number of distinct bit states and $k$ is the number of available pulses. The next $k$ lines describe the pulses; the $i$-th line describes the $i$-th pulse. The description of a pulse $f$ is a sequence of integers $f(0)\ \dots\ f(n-1)$ telling how $f$ acts on the state of each memory bit. These numbers are separated by single spaces.

Print $T$ lines to standard output, one per data set. The $i$-th line should contain the single word TAK (yes) if the memory can be zeroed for the $i$-th test, or NIE (no) otherwise.