Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_07_03 - Bieg

Polski SPOJ słynie z corocznej organizacji dwóch znakomitych imprez: rozgrywek AlgoLigi 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 109 metrów (meta znajduje się na 109 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 lato, co oznacza najwyższą porę na pozbycie się zbędnych kilogramów w jakie obrośliśmy przygotowując zadania do VII rundy AlgoLigi 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 ≤ 109; ab) 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

Dodane przez:Maciej Boniecki
Data dodania:2013-06-06
Limit czasu wykonania programu:0.100s-0.300s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.