Never Say Never

"How on earth am I supposed to set my employees' salaries?" wondered director Karierowitch. "I want everyone paid in proportion to their effectiveness. But effectiveness keeps changing, and surely I will never have two employees with exactly the same effectiveness at the same time."

Many years have passed since then. In total, $N$ employees have worked at the company over its history. Employee $i$ is described by four integers $s_i$, $e_i$, $a_i$, $b_i$: the employee was hired at time $s_i$, left the company (or the company let them go) at time $e_i$, and at any moment $t$ their effectiveness equals $a_i \cdot t + b_i$.

Determine whether there was ever a moment in the company's history at which two employees who were both employed at that moment had exactly the same effectiveness.

• $a_i$ may be negative.
• Effectiveness may be negative (the employee is harming the company instead of generating profit).
• Every employment interval $[s_i, e_i]$ is closed at both ends, and you must consider every real-valued moment $t$, not only integer ones.

The first line contains an integer $Z$ ($1 \le Z \le 10$), the number of test sets. The test sets follow.

The first line of each test set contains an integer $N$ ($1 \le N \le 10^5$), the number of employees in the company's history. Each of the next $N$ lines contains four space-separated integers $s_i$, $e_i$, $a_i$, $b_i$, where $0 \le s_i, e_i \le 10^6$ and $-10^6 \le a_i, b_i \le 10^6$.

For each test set, print on its own line "TAK" if there exists a moment at which some pair of simultaneously employed employees had the same effectiveness, and "NIE" otherwise.