Masala A

Sunnat online xaridlarni yoqtiradi. Yaqin $10^9$kun ichida pochta markaziga Sunnatning nomiga $n$ ta yuk kelishi kerak. Keling keyingi  $10^9$kunlarni raqamlaylik: 1-kun, 2-kun, ..., $10^9$-kun.  $i$-yuk pochta markaziga $l_i$-kun keladi, va bu yukni pochta markazidan olib ketish uchun oxirgi kun $r_i$-kundir. Bu degani, Sunnat usbhu yukni $x$-kun olib ketoladi, agarda $l_i \leq x \leq r_i$ sharti bajarilsa. Sunnat pochta markaziga bir marta kelganida uyiga eng ko'pi bilan $k$ tagacha yuk olib ketoladi. E'tibor bering, Sunnat bir kun davomida pochta markaziga bir necha marta borib kelishi mumkin. Sunnat minimal necha marta pochto markaziga borgan holda, barcha yuklarini uyiga olib keta oladi.

Birinchi qatorda bitat butun son - $T(1 \leq T \leq 3000)$ testlar soni kiritiladi.

Har bitta test uchun birinchi qatorda $n$ va $k(1 \leq k \leq n \leq 100000)$ kiritiladi. Keyingi $n$ ta qatorning har bitida ikkita butun son $l_i$ va $r_i(1 \leq l_i \leq r_i \leq 10^9)$ kiritiladi.

Barcha testlar kesimida $n$ larning summasi $10^6$ dan oshmasligi kafolatlanadi.

Har bitta test uchun alohida qatoda, Sunnat pochta markazida eng kamida necha marta borishi kerakligini chiqaring.