AlgoLiga 2018

Na kilku ostatnich lekcjach matematyki cała klasa Janka z zainteresowaniem słuchała Pani Basi, która tłumaczyła, jak wykonywać różne konstrukcje geometryczne sposobem klasycznym, czyli przy użyciu jedynie cyrkla i linijki. Dzieci potrafią już np. wyznaczyć środek danego odcinka, dwusieczną kąta, a nawet prostą równoległą do danej prostej tak, aby przechodziła przez pewien określony punkt.

Dzisiejsza lekcja dotyczyła wielokątów foremnych. Pani Basia pokazała jak skonstruować trójkąt równoboczny i kwadrat o bokach równych danemu odcinkowi. Pani poprosiła też, aby jako zadanie domowe, dzieci spróbowały skonstruować inne wielokąty foremne. Janek bez problemu wykreślił sześciokąt foremny, a jako bardzo zdolny uczeń poradził sobie też z konstrukcją pięciokąta. Utknął jednak przy siedmiokącie.  I tu nasunęły mu się pytania: Czy samym cyrklem i linijką da się skonstruować każdy wielokąt foremny? A jeśli nie, to które można? Janek doszedł więc do wniosku, że przydałby mu się program, który obliczy ile wielokątów foremnych z danego zbioru, da się skonstruować w klasyczny sposób, czyli jedynie cyrklem i linijką.

Wejście

W pierwszej linii liczba t (0 < t ≤ 1000000) oznaczająca liczbę zbiorów wielokątów foremnych (przypadków testowych).
W każdej z kolejnych t linii dwie liczby całkowite a i b (3 ≤ a ≤ b ≤ 2⁶⁴–1) oznaczające, że rozpatrujemy zbiór, w którym znajduje się b–a+1 różnych (co do liczby boków) n-kątów foremnych, takich że a ≤ n ≤ b.

Wyjście

Dla każdego przypadku testowego jedna liczba całkowita oznaczająca ile wielokątów z tego zbioru można skonstruować przy użyciu jedynie cyrkla i linijki.

Przykład

Wejście:
3
3 8
15 17
180 190

Wyjście:
5
3
0