Jewel heist
Arsen Lupin, məşhur oğru, Şər Ervinin zərgərlik əşyalarını oğurlamağı planlaşdırır. Ervinin mağazasında nümayiş etdirilən n qiymətli daş var. Hər bir daş k fərqli rəngdən birinə aiddir. Nümayiş o qədər böyükdür ki, onu Evklid müstəvisi kimi qəbul edə bilərik və daşlar fərqli nöqtələrdə yerləşir. Nümayiş olduqca bahalı siqnallarla qorunur.
Lupin bir cihaz icad edib: böyük, robotik əl, Ervinin bəzi daşlarını siqnalları işə salmadan götürə bilər. Əl bir (və yalnız bir) tutuş edə bilər, bəzi üfüqi seqmentdə və ya onun altında olan bütün daşları götürə bilər (şəkilə baxın). Lupin bu yolla asanlıqla bütün daşları götürə bilərdi, amma o bilir ki, nə qədər çox götürsə, onlardan qurtulmaq bir o qədər çətin olacaq. O, ən təhlükəsiz yolun bütün k rəngləri ehtiva etməyən bir dəst daş götürmək olduğuna qərar verdi.
Şəkil 1. Robotik əl 1, 2, 4, 5 və 6 nömrəli daşları götürür, qara olanları diqqətlə atlayır
Lupin cihazının bir tutuşu ilə, hər rəngdə daş götürmədən, neçə daş oğurlaya biləcəyini hesablayın.
Giriş verilənləri
Girişin ilk sətri test hallarının sayı T ilə başlayır. Test halları təsvirləri aşağıdakı kimidir:
Hər bir test halı iki tam ədəd n (2 ≤ n ≤ 200000) və k (2 ≤ k ≤ n) ilə başlayır, daşların sayı və fərqli rənglərin sayını göstərir. Növbəti n sətir daşların mövqelərini və rənglərini göstərir. j-ci sətir üç boşluqla ayrılmış tam ədəd x_j, y_j, c_j (1 ≤ x_j, y_j ≤ 10^9, 1 ≤ c_j ≤ k) ehtiva edir, bu o deməkdir ki, j-ci daş (x_j, y_j) koordinatlarında yerləşir və c_j rənginə malikdir.
Nümayişdə hər rəngdən ən azı bir daş olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Test halları girişdə göründüyü ardıcıllıqla cavabları çap edin. Hər bir test halı üçün oğurlana biləcək maksimum daş sayını ehtiva edən bir sətir çap edin.