시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB21141164.706%

문제

Silnia liczby N (oznaczana N!) to wartość iloczynu kolejnych liczb naturalnych dodatnich od 1 do N włącznie, tzn. 1 · 2 · . . . · N. Mamy zatem 1! = 1, 2! = 1 · 2, 3! = 1 · 2 · 3 = 6 oraz 4! = 1 · 2 · 3 · 4 = 24, itd.

Liczbę nazwiemy silną, jeśli jest sumą jednej lub wielu parami różnych silni. Na przykład liczba 25 = 24 + 1 = 4! + 1! jest liczbą silną, tak samo liczba 6 = 3! natomiast liczba 5, ani liczba 4 nie jest. Zwróć uwagę że w przypadku liczby 4, 4 = 2! + 2!, ale te dwie silnie nie są różne, zatem 4 nie jest liczbą silną.

Dla zadanych przedziałów [A, B], oblicz ile wynosi suma liczb silnych mieszczących się w tych przedziałach (wliczając A oraz B).

입력

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q (1 ≤ Q ≤ 100 000) określająca liczbę zapytań. W kolejnych Q wierszach znajdują się kolejne zapytania: pary liczb całkowitych A i B (1 ≤ A ≤ B ≤ 1013).

출력

Twój program powinien wypisać na wyjście Q wierszy. W i-tym powinna się znaleźć odpowiedź dla i-tego zapytania w kolejności w jakiej występują na wejściu: suma liczb silnych w przedziale [A, B].

예제 입력 1

2
1 10
5 8

예제 출력 1

36
21

Wyjaśnienie do przykładu: Rozważmy pierwsze zapytanie: w przedziale [1, 10] są następujące liczby silne: 1 = 1!, 2 = 2!, 3 = 1! + 2!, 6 = 3!, 7 = 3! + 1!, 8 = 3! + 2!, 9 = 3! + 2! + 1!. Ich suma to: 1 + 2 + 3 + 6 + 7 + 8 + 9 = 36. Dla drugiego zapytania, liczby silne to 6, 7 oraz 8, a ich suma to 6 + 7 + 8 = 21.

예제 입력 2

4
100 150
700 750
5000 5050
999995 1000000

예제 출력 2

1728
9528
40356
0

예제 입력 3

2
6000000000 7000000000
9999999999990 10000000000000

예제 출력 3

26576891725824
0