Problem description

Ciąg złożony jest to ciąg składający się wyłącznie z liczb złożonych. W ciągu kolejnych liczb naturalnych istnieje wiele takich ciągów złożonych występujących jako spójne podciągi. Jednak jedne z nich są dłuższe, a inne krótsze. Żeby było zadanie jakieś sensowne, będziemy się pytali o najdłuższe spójne podciągi złożone w ciągu kolejnych liczb naturalnych na jakimś wybranym kawałku.

Napisz program, który: wczyta zapytania o wybrane kawałki ciągu liczb naturalnych, wyznaczy dla każdego zapytania długość najdłuższego podciągu złożonego i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zapytań. W kolejnych Q wierszach znajduje się opis kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb naturalnych A_i i B_i określających, że i-te zapytanie dotyczy kawałka od liczby A_i do B_i włącznie.

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź dla każdego zestawu danych to jedna liczba całkowita — długość najdłuższego spójnego podciągu złożonego w ciągu z zapytania.

1 ≤ Q ≤ 100 000, 1 ≤ A_i ≤ B_i ≤ 4 000 000.

W testach wartych łącznie 30% maksymalnej punktacji: 1 ≤ Q ≤ 10.
W testach wartych łącznie 50% maksymalnej punktacji: 1 ≤ A_i ≤ B_i ≤ 500 000.

Przykład

3
4 14
5 7
2 3

3
1
0