Divisors

Time limit2sMemory limit512 MB

Summary

Given n and an expression built from divisors of n with gcd and lcm, decide whether the expression's value is the same for every assignment of variables.

Level: Hard8 of 10
Topics: Number theory, Tree, Math, Recursion
Solved: No attempts yet

Problem

We are interested in the divisors of a given natural number $n$ . Let $D(n)$ denote the set of all divisors of $n$ . We are given an expression built from constants taken from $D(n)$ , variables that may take any value in $D(n)$ , and two binary functions that compute the greatest common divisor and the least common multiple.

For a given expression, decide whether its value is the same for every possible assignment of values to the variables, that is, whether the expression denotes a constant function.

Input

The first line contains an integer $t$ ( $1 \le t \le 1000$ ), the number of test cases. Each of the next $t$ lines describes one test case.

Each description starts with an integer $n$ ( $1 \le n \le 10^{18}$ ), followed by the description of the expression. An expression is a constant, a variable, or a function application.

Each number is a constant and is a positive divisor of $n$ .
A variable is a sequence of at most $5$ lowercase English letters; identical sequences denote the same variable.
The names NWD and NWW denote the functions computing the greatest common divisor and the least common multiple, respectively. A function name is followed by a single space and then the space-separated descriptions of its two arguments, each of which is itself an expression (so the description is recursive).

The total size of the input does not exceed $2$ MB.

Output

Print $t$ lines, one answer per test case. For each test case print TAK (Polish for yes) if the expression denotes a constant function regardless of the variable values, and NIE (Polish for no) otherwise.

Examples5

Example 1

Input

3
24 NWD 3 NWW x 12
15 NWD 15 nwd
10 10

Expected output

TAK
NIE
TAK

Example 2
Input
```
3
1 1
1 NWD x y
100 50
```
Expected output
```
TAK
TAK
TAK
```

Example 3

Input

4
100 x
20 NWD z 20
20 NWD z 1
12 NWW y 12

Expected output

NIE
NIE
TAK
TAK

Example 4

Input

2
8 NWD 2 NWW x 2
8 NWW 2 NWD x 2

Expected output

TAK
TAK

Example 5
Input
```
2
12 NWW 6 NWD x 4
12 NWD z 6
```
Expected output
```
NIE
NIE
```