Due to an unfortunate series of events (and a certain malicious bug in the student management system), Bajtazar is doing his student internship this year in an archaeological laboratory. He is currently trying to reconstruct a certain ancient mosaic, of which very little has survived – it is known that it was originally in the shape of a rectangle, divided into $n$ square tiles of potentially different sizes. Unfortunately, the dimensions of the rectangle and the side lengths of the squares are unknown. The only thing that can be deduced from historical sources is the positions of the bottom-left corners of the tiles.

As it turns out, even archaeologists sometimes need the help of programmers! Given the positions of the bottom-left vertices (i.e., $n$ points on a plane), find $n$ squares with sides parallel to the coordinate axes such that:

• all squares form a single rectangle;
• the interiors of any two squares have no common points;
• the bottom-left vertex of the $i$-th square coincides with the $i$-th of the given points.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 50$) – the number of test cases. Then $t$ descriptions of test cases follow, in the format given below:

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) – the number of points in the test case. The next $n$ lines each contain two integers $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – the coordinates of the $i$-th point. No two points in a single test case coincide.

The total number of points across all test cases in a single run does not exceed $5000$.

Output

For each of the $t$ test cases, output one line. If no such arrangement of squares exists for a given test case, output the word NIE. Otherwise, output the word TAK, followed by $n$ positive integers separated by single spaces; the $i$-th of these numbers should denote the side length of the $i$-th square in the solution. This number should not exceed $2 \cdot 10^9$. You may assume that if a test case has a solution, it specifically has one where each square has a side length no greater than $2 \cdot 10^9$.

If there is more than one solution, output any one of them.

Examples

Input 1

3
2
0 0
0 1
2
3 2
2 3
4
1 1
2 1
3 1
1 2

Output 1

TAK 1 1
NIE
TAK 1 1 3 2