Masala #0736

Xotira 16 MB Vaqt 1000 ms
14

Graf ichidan to'plam

Sizga Grafning tugunlar soni \(N\) berilgan. Grafdagi tugunlar 1 dan N gacha nomerlangan. Grafda barcha \(u \% v == 0 (2 \le u, v \le n)\) shartni qanoatlantiradigan tugunlar orasida to’g’ridan to’g’ri yo’l mavjud. Siz quyidagi shartlarni qanoatlantiradigan to’plamni hosil qiling:

  • To’plam elementlar soni imkon qadar kam bo’lsin
  • Grafning barcha tuguni uchun quyidagi shartlardan biri bajarilsin:
    • Tugun to’plam ichida mavjud bo’lsin
    • Tugun bilan to’g’ridan to’g’ri yo’l mavjud bo’lgan boshqa bir tugun to’plam ichida mavjud bo’lsin

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10^5)\) testlar soni kiritiladi.

Keyingi \(T\) ta qatorda bittadan butun son, \(N (1 \le N \le 10^6)\) graf tugunlar soni kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda hosil qilingan to’plamning minimal uzunligi nechchi bo’lishini chop eting!


Misollar
# input.txt output.txt
1
1
6
4
Izoh:

1-testda:
Grafda 2-4, 2-6, 3-6 yo’llar mavjud
To’plamni (1,4,5,6) qiymatlardan hosil qilsa bo’ladi.