AlgoLiga 2018

Danych jest n parami różnych punktów o współrzędnych całkowitych na płaszczyźnie oraz liczba całkowita dodatnia k. Należy stwierdzić, czy wszystkie punkty można pokryć używając k prostych.

Wejście

W pierwszej linii znajduje się liczba naturalna T (1<=T<=30) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

Pojedynczy zestaw testowy zbudowany jest następująco:
- w pierwszej linii znajduje się liczba punktów n (1<=n<=20000) i liczba prostych k (1<=k<=5),
- w kolejnych n liniach znajdują się współrzędne x y kolejnych punktów, |x|, |y|<=10⁹.

Wyjście

Dla każdego zestawu testowego należy w osobnej linii wypisać "TAK" lub "NIE" - odpowiedź na pytanie z treści zadania.

Przykład

Input:
3
4 1
0 0 
2 2
11 11
-2 -2
3 1
1 0
0 0 
0 1
3 2
1 0
0 0 
0 1

Output:
TAK
NIE
TAK