The Existence of N

Time limit5sMemory limit128 MB

Summary

Given a prime p, exponent m, and residue a, decide whether some positive n makes n^n + n^m congruent to a mod p.

Level: Medium7 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

You are given a prime $p$ , a positive integer $m$ , and an integer $a$ with $0 \le a < p$ .

Determine whether there exists a positive integer $n$ such that $n^n + n^m \equiv a \pmod{p}$ .

Input

The first line contains the number of test cases $d$ ( $1 \le d \le 300$ ).

Each of the next $d$ lines contains three integers $p$ , $a$ , and $m$ ( $2 \le p \le 10^9$ , $0 \le a < p$ , $1 \le m \le 20$ , $m < p$ ). $p$ is always prime.

Output

For each test case, print one line. If there exists a positive integer $n < 10^{1000}$ satisfying $n^n + n^m \equiv a \pmod{p}$ , print TAK; otherwise print NIE.

Examples2

Example 1
Input
```
2
11 3 1
11 8 2
```
Expected output
```
TAK
TAK
```
Example 2
Input
```
2
2 1 1
2 0 1
```
Expected output
```
NIE
TAK
```