Rikka with Defensive Line

Problem Description

As an undergraduate student at Peking University, Rikka is always busy with her study. Therefore, to relax in the summer vacation, Rikka spends a lot of time playing computer games. Today, Rikka is playing a game about a war between two tribes. As the player, Rikka controls the warriors of one tribe to attack the other tribe. The hostile tribe has $n$ strongholds, and the coordinate of the $i$th stronghold is $(x_i,y_i)$. A defensive line is built among the strongholds: it is a straight line on the coordinate system which divides the whole plane into two regions. The first goal of the game is to capture this defensive line. As a sophisticated player, Rikka finds that if some of the strongholds are destroyed and all of the remaining strongholds are strictly lying on the same side of the defense line (lying exactly on the defensive line is not allowed), she can capture the defense line with a very small price. Therefore, Rikka will firstly achieve this condition by destroying the minimum number of strongholds at the beginning of the game. After repeating the game $10^{100}$ times, Rikka finds that she can always achieve the goal by destroying at most $K$ strongholds. She is curious about this phenomenon. Therefore, Rikka asks Yuta, a master of information technology, to read the source code of the game and find out the reason. Yuta finds that while initializing, the game will always choose two strongholds and make the defensive line be the only straight line passing through them. Then, to decrease the difficulty, the game will check whether the "easy condition" (i.e., the condition found by Rikka) can be achieved by destroying at most $K$ strongholds: If not, the game will repeat the initialize process until the chosen defensive line is valid. After observing this secret, Rikka gives the map of the games to you, i.e., the coordinates of the strongholds. For each stronghold $x$, Rikka wants you to calculate the number of other strongholds $y$ so that line $x,y$ is a valid defensive line.

Input

The first line of the input contains a single integer $T(1 \leq T \leq 50)$, the number of test cases. For each test case, the first line contains two positive integers $n,K(1 \leq n \leq 5 \times 10^4, 1\leq K \leq 50)$, the number of strongholds and the secret constant in the source code. Then $n$ lines follow, each line with two integers $x_i,y_i(|x_i|,|y_i| \leq 10^8)$, which represents the coordinates of the strongholds. The input guarantees that there are no more than $2$ test cases with $n > 1000$ and no two strongholds share the same $x$ coordinate or $y$ coordinate, i.e., for any two different strongholds $i,j$, $x_i \neq x_j$ and $y_i \neq y_j$.

Output

For each test case, output the single line with $n$ integers which represent the answer for each stronghold. Hint In the first two test cases, only the $(1,2),(2,3),(3,4),(1,4)$ are valid defensive lines where $(a,b)$ represents the straight line passing through the $a$th and $b$th strongholds. In the third test case, any pair of strongholds can from a valid defensive line.

Sample Input

3

5 2

1 0

4 1

3 4

0 3

2 2

5 3

1 0

4 1

3 4

0 3

2 2

5 4

1 0

4 1

3 4

0 3

2 2

Sample Output

2 2 2 2 0

2 2 2 2 0

4 4 4 4 4

Source

2019 Multi-University Training Contest 9