Masala #PD4SRZZUM6

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 5 %

Minimal KOPRIM

Bugun Kichik Samir barcha jamg'armasini bir segment sotib olishga sarfladi. U ushbu segmentda uy qurmoqchi.
Ijobiy sonlar segmenti [l,r] koprim deyiladi, agar l va r koprim bo'lsa.

Koprim segment [l,r] minimal koprim deb ataladi, agar u o'z ichiga o'zidan boshqa hech qanday koprim segmentni olmasa. Ushbu bayonotni yaxshiroq tushunish uchun izohlar qismiga murojaat qilishingiz mumkin.

Sizga ijobiy sonlar segmenti [l,r] berilgan. Ushbu segment ichida nechta minimal koprim segment borligini toping.

Kiruvchi ma'lumotlar:

Har bir testda bir nechta test holatlari mavjud.
Birinchi qatorda test holatlari soni t \((1 \leq t \leq 100)\) keltiriladi.

Keyingi qatorlarning har birida ikkita butun son l va r \((1≤l≤r≤109)\) beriladi.

Chiquvchi ma'lumotlar:

Har bir test holati uchun alohida qatorda [l,r] segment ichidagi minimal koprim segmentlar sonini chop eting.

Misollar

#	input.txt	output.txt
1	6 1 2 1 10 49 49 69 420 1 1 9982 44353	1 9 0 351 1 34371

Izoh:

Birinchi test holatida berilgan segment [1,2]. Ushbu segment ichida quyidagi segmentlar mavjud:

[1,1]: Bu koprim segment, chunki 1 va 1 koprim va segment ichida boshqa koprim segment yo'q. Demak, bu minimal koprim.
[1,2: Bu segment koprim, lekin u [1,1] ni o'z ichiga oladi. Shu sababli, bu minimal emas.
[2,2]: Bu segment koprim emas, chunki 2 va 2 1 va 2 musbat umumiy bo'luvchilarga ega.

Shunday qilib, segment [1,2] ichida faqat 1 ta minimal koprim segment mavjud.

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin