Mama Bajtolina loves her Bajtoniątka very much. However, she is a bit forgetful, so instead of giving them names, she numbered them with natural numbers from $1$ to $n$ for convenience. Every day, she prepares dinner for her Bajtoniątka, and for dinner, she brews tea for each Bajtoniątko in its favorite mug. The mugs have different capacities: the $i$-th Bajtoniątko's mug has a capacity of $l_i$ liters, which is exactly how much the $i$-th Bajtoniątko likes to drink for dinner. The volume of tea is not the only requirement of the Bajtoniątka – the temperature of the tea must also be appropriate. The $i$-th Bajtoniątko would like its tea to have a temperature of exactly $b_i$ degrees Bajtsjusza.

Unfortunately, one evening, the forgetful Bajtolina mixed everything up, and the temperature of the tea in the $i$-th mug is exactly $a_i$ degrees Bajtsjusza. However, all is not lost – the Bajtoniątka are very clever and, using additional mugs, they started pouring, mixing, and swapping teas. The question is: is it possible for the Bajtoniątka to achieve their goal in this way, i.e., to obtain $n$ teas, where the $i$-th one will have a volume of $l_i$ liters and a temperature of $b_i$ degrees Bajtsjusza?

Formally, the Bajtoniątka can perform the following two steps a finite number of times:

• Dividing tea. Having a mug containing $a$ liters of tea at a temperature of $t$ degrees, they can, for any real number $x$ such that $0 < x < a$, divide it into two mugs containing $x$ and $a - x$ liters of tea, respectively, both at a temperature of $t$ degrees.
• Mixing tea. Having two mugs containing $a$ and $b$ liters of tea at temperatures of $t_a$ and $t_b$ degrees, respectively, they can mix them, obtaining one mug containing $a+b$ liters of tea at a temperature of $$\frac{a \cdot t_a + b \cdot t_b}{a + b}$$ degrees, which is the weighted average of both temperatures.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 100\,000$), denoting the number of test cases.

The description of each test case begins with a line containing an integer $n$ ($1 \le n \le 100\,000$), denoting the number of Bajtoniątka. This is followed by $n$ lines describing the Bajtoniątka; the $i$-th of these contains three integers $l_i$, $a_i$, and $b_i$ ($1 \le l_i, a_i, b_i \le 1\,000\,000$), denoting the volume of tea in liters and the initial and required temperature in degrees Bajtsjusza for the $i$-th Bajtoniątko, respectively.

The sum of $n$ over all test cases will not exceed $1\,000\,000$.

Output

For each test case, output one line containing the word TAK or NIE, depending on whether the Bajtoniątka can achieve their goal in the $i$-th test case.

Examples

Input 1

5
2
2 1 4
2 5 2
2
1 4 3
1 5 4
2
1 5 7
1 7 5
2
1 4 1
1 2 5
3
2 6 4
1 2 3
3 4 5

Output 1

TAK
NIE
TAK
NIE
TAK

Note

Explanation of the example: Let us denote individual mugs of tea as pairs of numbers. The pair $(l, t)$ denotes a mug with $l$ liters of tea at a temperature of $t$ degrees Bajtsjusza.

In the first test case, the Bajtoniątka initially have mugs $(2, 1)$ and $(2, 5)$. By dividing the tea, they can obtain a set of mugs $(\frac{1}{2}, 1), (1\frac{1}{2}, 1), (\frac{1}{2}, 5), (1\frac{1}{2}, 5)$. Then, by mixing the mugs $(\frac{1}{2}, 1)$ and $(1\frac{1}{2}, 5)$, they obtain $\frac{1}{2} + 1\frac{1}{2} = 2$ liters of tea at a temperature of $$\frac{\frac{1}{2} \cdot 1 + 1\frac{1}{2} \cdot 5}{\frac{1}{2} + 1\frac{1}{2}} = 4,$$ which is the mug $(2, 4)$. Similarly, by mixing $(1\frac{1}{2}, 1)$ with $(\frac{1}{2}, 5)$, they obtain $(2, 2)$. Ultimately, the Bajtoniątka will possess exactly two mugs with the appropriate volumes and temperatures.

In the second test case, both teas of the Bajtoniątka are too hot. Unfortunately, neither dividing nor mixing will help here.

In the third test case, it is enough for the Bajtoniątka to swap mugs.

Subtasks

In some test groups (at least one), all values $l_i$ are exactly $1$. In other words, all mugs have a capacity of exactly one liter.