C. Давхар аз жаргал

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 128 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Тооны хичээл дээр багш сурагч бүрээс азын тоог нь асуув. Тооны онолын хорхойтон Петр анхны тоонуудыг сонгов. Харин Боб илүү өвөрмөц байв. Тэр $t$ тоог $t = a^2 + b^2$ хэлбэрт тавьж болдог тохиолдолд азын гэж үзнэ гэв(энд $a, b$ тоонууд нь дурын тоо).

Одоо хөвгүүд $[l, r]$ ($l ≤ r$) завсарын хэдэн өдөр нь хос програмчлалд тохиромтой вэ гэдгийг мэдэхийг хүсэв. Хэрэв $i$ ($l ≤ i ≤ r$) тоо нь Петрийн болон Бобын азын тоо зэрэг болж чаддаг тохиолдолд хос програмчлалд тохиромжтой гэж үзэхээр шийдэв. Хөвгүүдэд дараах нөхцөлийг хангах хэдэн тоо байгааг олоход нь тусла.

Оролт

Эхний мөхөнд $l, r$ ($1 ≤ l, r ≤ 3·10^8$) тоонууд өгөгдөнө.

Гаралт

$[l, r]$ завсарт орших Петр Боб 2-ын азтай тоо зэрэг болж чадах тооны тоог ол.

Орчуулсан: Энхсанаа

Жишээ тэстүүд

Оролт
3 5
Гаралт
1
Оролт
6 66
Гаралт
7
Сэтгэгдлүүдийг ачааллаж байна...