AlgoLiga 2018

Jaś ćwiczy się w mnożeniu modularnym i oblicza iloczyny kolejnych liczb naturalnych z pewnych przedziałów. Potrzebuje więc programu, którym baaardzo szybko sprawdzi poprawność swoich obliczeń. Jego napisanie to Twoje zadanie.

Wejście

W pierwszej linii liczba przypadków testowych t (t ≤ 10).

W każdej z kolejnych t linii, dwie liczby całkowite a i b (1 ≤ a ≤ b ≤ 4·10¹⁸, b–a ≤ 1000) oznaczające odpowiednio pierwszą i ostatnią liczbę z ciągu kolejnych liczb naturalnych, których iloczyn należy obliczyć.

Wyjście

Dla każdego przypadku testowego, w osobnej linii, wyznaczony iloczyn modulo 4611686018427387847.

Przykład

Wejście:
2
1 10
3900000000000000000 3900000000000001000

Wyjście:
3628800
3839422463663209647