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.

Yechim yuborish uchun tizimga kiring yoki ro'yxatdan o'ting.

Navbatdagi musobaqa

Biriktirilgan musobaqa

SamCoding Round 11 (Div. 1)

Natijalar