Bajtazar's company produces wooden wardrobes with mirrored doors. The company focuses on the quality of the wooden products and outsources the production of mirrors to subcontractors.

A tender organized by Bajtazar's company has just concluded. $n$ factories participated in it, each submitting an offer regarding the dimensions of the mirrors they produce. All mirrors are rectangular. Each factory's offer specifies the minimum and maximum width and the minimum and maximum height of the mirrors they produce. Mirrors cannot be rotated during wardrobe production.

Bajtazar knows that if a factory participates whose offer majorizes the offers of all others—meaning no other bidder offers a mirror size that this factory does not also produce—then that factory will certainly win the tender (if multiple factories have a majorizing offer, the one offering the lowest price per square centimeter of mirror will win). Otherwise, the evaluation of the offers will be complicated, and the resolution of the tender will be significantly delayed. Hoping to avoid fruitless discussions, Bajtazar has asked you to write a program that determines whether any factory's offer majorizes the offers of all other factories.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10$), representing the number of test cases to consider. The descriptions of the subsequent test cases follow.

The first line of each description contains a single integer $n$ ($2 \le n \le 100\,000$), representing the number of mirror production factories that submitted offers in the tender organized by Bajtazar's company. Each of the following $n$ lines contains four integers $w_1, w_2, h_1, h_2$ ($1 \le w_1 \le w_2 \le 10^9$, $1 \le h_1 \le h_2 \le 10^9$). These numbers indicate that the given factory can produce mirrors of any integer width $w$ and height $h$ satisfying $w_1 \le w \le w_2$ and $h_1 \le h \le h_2$.

Output

Your program should output exactly $t$ lines, containing the answers for the individual test cases. The $i$-th line should contain the word TAK or NIE, depending on whether a factory participated in the tender whose offer majorizes the offers of all other bidders.

Examples

Input 1

3
3
2 3 3 5
1 4 2 6
1 3 4 6
3
1 5 1 3
2 4 1 3
3 4 2 5
4
1 2 1 10
1 2 3 8
2 2 7 10
1 2 1 10

Output 1

TAK
NIE
TAK