Muallif: __thecrash__
A. Chiroqlar va kalitlar
Vaqt limiti: 1000 ms Xotira limiti: 128 mb
Yangi qurilgan ulkan ko'rgazma zalida bir qatorga juda ko'p chiroq o'rnatildi. Chiroqlar \(1\) dan \(10^{18}\) gacha raqamlangan, boshida hammasi o'chiq. Zal devorida ham xuddi shuncha kalit bor, ular ham \(1\) dan \(10^{18}\) gacha raqamlangan.
\(i\)-kalit bosilganda raqami \(i\) ga bo'linadigan barcha chiroqlarning holati o'zgaradi, ya'ni yoniq chiroq o'chadi, o'chiq chiroq yonadi. Zal ochilishi oldidan elektrik barcha kalitlarni \(1\)-kalitdan boshlab tartib bilan bir martadan bosib chiqdi.
Endi zal mudiri tekshiruv o'tkazmoqchi. U \(t\) marta so'raydi, har safar \(l\) va \(r\) sonlari aytiladi. Raqami \(l\) dan \(r\) gacha bo'lgan chiroqlardan nechtasi yonib turganini aniqlang.
Kiruvchi ma'lumotlar
Birinchi qatorda bitta butun son \(t\) (\(1 \le t \le 10^5\)), so'rovlar soni.
Keyingi \(t\) ta qatorning har birida ikkita butun son \(l\) va \(r\) (\(1 \le l \le r \le 10^{18}\)).
Chiquvchi ma'lumotlar
Har bir so'rov uchun alohida qatorda \(l\) dan \(r\) gacha bo'lgan oraliqda yonib turgan chiroqlar sonini chiqaring.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
| 1 |
3 1 8 5 8 99999999 100000000 |
2 0 1 |
Izoh
Birinchi so’rovda \(1\) va \(4\)-chiroqlar yonib turadi. Masalan, \(4\)-chiroq holatini \(1\), \(2\) va \(4\)-kalitlar o’zgartiradi, shuning uchun u yonib qoladi.
Ikkinchi so'rovda \(5\) dan \(8\) gacha bo'lgan chiroqlarning hammasi o'chiq.