Cho hai số $l,r$ thoả mãn $2\le l\le r\le {10}^{12}$. Bạn hãy tìm số $k$ nguyên dương lớn nhất sao cho tồn tại số nguyên dương $x$ thoả mãn $l\le x^k\le r$.

Input

• Dòng đầu là số bộ test $t$ $(t\le 5000)$.
• Mỗi dòng tiếp theo chứa hai số nguyên dương $l,r$.

Output

Kết quả mỗi bộ test in trên một dòng.

Ví dụ

Input

4
4 21
10 12
5 100
1000000000000 1000000000000

Output

4
1
6
12

Giải thích

• $4\le 2^4\le 21$ => $k=4$
• $10\le {12}^1\le 12$ => $k=1$
• $5\le 2^6\le 100$ => $k=6$
• ${10}^{12}\le {10}^{12}\le {10}^{12}$ => $k=12$