Talulu đang chơi một trò chơi trí tuệ cùng bạn mình là Cheow. Cậu ấy chọn một khoảng số từ ~L~ đến ~R~, sau đó đố Cheow tìm ra số nguyên dương lớn nhất ~K~ sao cho tồn tại một số nguyên dương ~X~ thỏa mãn bất đẳng thức: ~L ≤ x^k ≤ R~

Cheow cần bạn giúp để chiến thắng trò chơi này. Bạn có thể viết chương trình để giúp cậu ấy không?

Input

• Dòng đầu tiên chứa một số nguyên ~T~ — số lượng test ~(1 ≤ T ≤ 10^4)~.
• Mỗi dòng tiếp theo chứa hai số nguyên ~L~ và ~R~ ~(2 ≤ L ≤ R ≤ 10^{12})~ — biểu diễn một truy vấn.

Output

• Với mỗi truy vấn, in ra ~k~ là giá trị lớn nhất thỏa mãn điều kiện đề bài.

📌 Example

Input

4
5 20
10 12
2 100
1000000000000 1000000000000

Output

4
1
6
12

💡 Explanation

• Test 1: Với ~k = 4~ thì ~x = 2~ là phù hợp vì 2^4 = 16 ∈ [5, 20]. Nếu ~k = 5~ thì ~2^5~ = 32 > 20 → không hợp lệ.
• Test 2: Chỉ có ~k = 1~ và ~x = 12~ mới thỏa.
• Test 4: Vì ~L = R = 10^{12}~ nên chỉ có thể chọn ~x^k = 10^{12}~, lớn nhất là ~k = 12~ với ~x = 10~.