Wstęp do programowania w C++

Rozważmy następujący algorytm generujący ciąg liczb całkowitych. Zaczyna się od liczby n. Jeżeli n jest parzyste, dzielimy je przez 2. W innym przypadku mnożymy przez 3 i dodajemy 1. Obliczenia powtarzamy dla nowej wartości n. Kończymy, gdy n=1. Na przykład dla n=22 generowany jest następujący ciąg liczb:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Przypuszcza się (choć nie zostało to jeszcze udowodnione), że algorytm ten zatrzymuje się z n=1 dla dowolnej liczby początkowej n. Rzeczywiście, hipoteza ta sprawdza się dla wszystkich liczb do co najmniej 1\ 000\ 000.

Dla danej liczby n długość wygenerowanego ciągu, włączając końcową liczbę 1, nazywamy długością cyklu dla n. W powyższym przykładzie długość cyklu dla 22 wynosi 16. Dla danych liczb i oraz j zadanie polega na wyznaczeniu maksymalnej długości cyklu dla wszystkich liczb między i a j, włączając obie te liczby.

Input

W pierwszym wierszu mamy liczbę par liczb, do wczytania. W kolejnych, ciąg par liczb całkowitych i i j, po jednej parze w wierszu. Wszystkie liczby sa mniejsze od 1 000 000 i wieksze od 0 oraz i <= j.

Output

Dla każdej danej pary liczb i, j wynik ma zawierać liczby i, j w tej samej kolejności, w jakiej pojawiają sie w danych wejściowych, a następnie maksymalna długość cyklu dla liczb od i do j włącznie. Te trzy liczby oddzielone spacjami (po jednej spacji między kolejnymi liczbami) powinny znajdowac się w jednym wierszu, wierszy z kolei powinno być tyle, ile było wierszy w danych wejściowych, bez uwzględniania pierwszego wiersza.

Example

Input:
4
1 10
100 200
201 210
900 1000

Output:
1 10 20
100 200 125
201 210 89
900 1000 174

Źródło: Wyzwania programistyczne, Steven S. Skiena, Miguel A. Revilla, Tłumaczenie: E. Kieroński, P. Rychlikowski, T. Truderung Edycja naukowa: Profesor L., Polkowski, T. Kaczorek, R. Schaefer, A. Skowron i R. Słowiński, WSiP, 2004