Problem description

To już trzecie zadanie z NWW. Czyżby autorom zadań na sparingi kończyły się pomysły? Zadanie jest tym razem bardzo krótkie: chcemy obliczyć najmniejszą wspólną wielokrotność kolejnych liczb w przedziale [A;B]: czyli NWW(A,A+1,…,B). Niestety, jest wiele zapytań do rozpatrzenia.

Napisz program, który: wczyta zapytania, dla każdego z nich obliczy najmniejszą wspólną wielokrotność i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna Q – liczba zapytań. W kolejnych Q wierszach znajdują się kolejne zapytania, każde z nich składa się z dwóch liczb A_i oraz B_i, oddzielonych pojedynczym odstępem – są to końce przedziału obustronnie domkniętego, którego dotyczy zapytanie.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym z nich powinna się znaleźć odpowiedź dla i-tego zapytania – reszta z dzielenia przez 10⁹ + 7 liczby NWW(A_i,A_i+1,…,B_i−1,B_i).

Ograniczenia

1 ≤ Q ≤ 50 000, 1 ≤ A_i ≤ B_i ≤ 50 000.

Przykład

4
1 5
3 6
5 5
10 12

60
60
5
660