Archiwum zadań programistycznych WWSI

Warszawska Wyższa Szkoła Informatyki słynie z corocznej organizacji dwóch znakomitych imprez: Mistrzostw WWSI w Programowaniu oraz Algorytmicznego Maratonu. Zapewne pierwszą z nich dosyć dobrze znasz, w końcu bierzesz w niej udział, natomiast odnośnie Algorytmicznego Maratonu winni jesteśmy kilka słów wyjaśnień. Jest to impreza rządząca się swoimi, dosyć charakterystycznymi, zasadami:

• wszyscy uczestnicy biegu startują ze wspólnej linii startu (oznaczonej jako metr zerowy) a ich celem jest zdobycie jak największej liczby punktów
• trasa biegu ma zawrotną długość wynoszącą dokładnie 10⁹ metrów (meta znajduje się na 10⁹ metrze)
• punkty przyznawane są w następujący sposób: zawodnik, który jako pierwszy pokona metr trasy o numerze porządkowym podzielnym przez 3 otrzymuje 3 punkty, analogiczna sytuacja ma miejsce w przypadku metra o numerze porządkowym podzielnym przez 5 (5 pkt) i 10 (10 pkt)
• w przypadku kiedy numer porządkowy danego metra podzielny jest przez dwie lub trzy liczby z poprzedniego punktu premia jest wymnażana (przykładowo za pokonanie piętnastego metra zawodnik otrzyma 15 pkt - 3×5, za 50 metr 50 pkt - 5×10 za 30 metr 150 pkt - 3×5×10, itd.).

Jako, że za oknem mamy już prawie wiosnę, co oznacza najwyższą porę na pozbycie się zbędnych kilogramów w jakie obrośliśmy przygotowując zadania do V MWWSIP postanowiliśmy wystartować w tegorocznej edycji maratonu. Jak wszyscy zawodnicy nie posiadający praktycznie żadnej kondycji swoją szansę upatrujemy wyłącznie w genialnej taktyce. Otóż nasza taktyka zakłada, iż przyspieszać będziemy na krótką chwilę w najkorzystniejszych ku temu momentach by zaraz po zrywie przepuścić rywali i nabrać nieco sił biegnąc w końcówce stawki. Aby zrealizować ten misterny plan potrzebujemy jednak dokładnych wyliczeń, musimy wiedzieć ile punktów jest do zdobycia w danym przedziale (w końcu jakoś musimy ustalić kiedy przyspieszać, a kiedy zwalniać). Jako, że mamy już serdecznie dosyć programowania i robienia różnych dziwnych obliczeń zwracamy się z tą prośbą właśnie do Ciebie! Pomóż nam i napisz program, który obliczy ile punktów można zdobyć biegnąc jako lider wyścigu na danym odcinku trasy.

Wejście

W pierwszej linii wejścia znajduje się liczba n (1 ≤ n ≤ 400000) określająca liczbę odcinków o które będziemy chcieli Cię zapytać. Każde z zapytań znajduje się w oddzielnej linii i składa się z dwóch liczb a oraz b (1 ≤ a, b ≤ 10⁹; a ≤ b) określających odpowiednio początek i koniec odcinka trasy.

Wyjście

Na wyjściu należy w oddzielnej linii dla każdego zapytania wypisać jedną liczbę - liczbę punktów jakie otrzyma zawodnik prowadzący wyścig przez całą długość zadanego odcinka.

Przykład

Wejście:

3
1 8
28 37
3 64

Wyjście:

11
161
601