Cho \(l, r\) sao cho \(2 \le l \le r \le 10^{12}\) Tìm số \(k\) nguyên dương lớn nhất sao cho tồn tại số nguyên dương \(x\) để \(l \le x^k \le r\)

Input

• Dòng đầu tiên là số lượng test.
• Mỗi dòng tiếp theo chứa hai số nguyên \(l,r\) biểu thị một test.

Output

• Số \(k\) lớn nhất tìm được tương ứng mỗi bộ test.

Example 1

4
5 20
10 12
2 100
1000000000000 1000000000000

Example 2

4
1
6
12