Một nhà máy ABC sản xuất hàng hóa theo dây chuyền tự động. Mỗi sản phẩm sau khi hoàn thiện sẽ gắn một mã hiệu duy nhất là một số nguyên dương được đánh số liên tiếp từ ~A~ đến ~B~ theo thứ tự xuất xưởng.

Tuy nhiên, do lỗi phần mềm trong quá khứ, các sản phẩm mà mã hiệu có số lượng ước dương là số lẻ thì có khả năng bị lỗi và cần loại bỏ khỏi danh sách kiểm kê.

Để phục vụ thống kê, kỹ sư trưởng yêu cầu bạn tính xem có bao nhiêu mã hiệu hợp lệ trong đoạn từ ~A~ đến ~B~.

Input

Một dòng duy nhất chứa hai số nguyên dương ~A, B (A \le B \le 10^18)~.

Output

In ra số nguyên duy nhất là số lượng các mã hiệu hợp lệ.

Sample Input

1 3

Sample Output

2

Giải thích

Số ~1~ là số có số lượng ước lẻ, ~2~ mã hiệu hợp lệ là số ~2~ và số ~3~.

Subtask

Có ~60\%~ số test ứng với ~60\%~ số điểm có ~A, B \le 10^3~.

Có ~20\%~ số test ứng với ~20\%~ số điểm có ~A, B \le 10^6~.

Có ~20\%~ số test ứng với ~20\%~ số điểm có ~A, B \le 10^{18}~.

Tháp là một chồng gồm các đĩa đồng trục đặt lên nhau sao cho đĩa có đường kính nhỏ luôn nằm trên đĩa có đường kính lớn hơn. Để có được hình dạng cân đối, đường kính các đĩa phải thỏa mãn một số điều kiện cụ thể. Tháp ước gọi là tháp ước số nếu mọi đĩa của tháp đều thỏa mãn điều kiện: Đường kính các đĩa đều là số nguyên dương và đường kính đĩa ở trên là ước số của đường kính nằm ngay dưới nó.

Tháp ước được gọi là tháp đầy đủ nếu không thể chèn được thêm đĩa nào vào giữa hai đĩa bất kỳ của tháp mà vẫn thỏa mãn tính chất tháp ước số.

Như vậy, với mỗi cặp số nguyên dương ~(a, b)~ mà ~a~ là ước của ~b~, một tháp đầy đủ của ~(a, b)~ là một chồng đĩa mà đường kính của chúng là dãy số nguyên dương ~x_1, x_2, \ldots, x_k~ sao cho:

• ~x_1 = a, x_k = b~;

• Với ~i = 1, 2, \ldots, k-1~:

  • ~x_i~ là ước của ~x_{i+1}~;
  • Đồng thời không tồn tại số nguyên ~y~ nào thỏa mãn ~x_i < y < x_{i+1}~, với ~x_i~ là ước của ~y~ và ~y~ là ước của ~x_{i+1}~.

Ví dụ: cặp ~(3, 36)~ thì dãy ~(3, 9, 18, 36)~ là một tháp đầy đủ; nhưng dãy ~(3, 12, 36)~ chưa đủ điều kiện trở thành tháp đầy đủ vì có thể chèn 6 vào giữa ~3~ và ~12~ để trở thành dãy ~(3, 6, 12, 36)~.

Chiều cao của tháp là số lượng đĩa có trong tháp, trọng số của tháp là tổng đường kính của các đĩa trong tháp: $x1 + x2 + \cdots + x_k$

Chẳng hạn, cặp số (3, 36), chúng ta có thể tìm được các tháp đầy đủ là:

• ~(3, 9, 18, 36)~, ~(3, 12, 36)~, ~(3, 6, 18, 36)~ đều có chiều cao tương ứng là ~4~ và trọng số lần lượt là ~66~, ~57~, ~63~.

Yêu cầu: Cho cặp ~(a, b)~ tìm chiều cao và trọng số của tháp đầy đủ có trọng số nhỏ nhất.

Input

Một dòng chứa hai số nguyên dương ~a~ và ~b~.

Output

• Ghi số ~-1~ nếu không thể tìm được tháp đầy đủ tương ứng với cặp ~(a, b)~;
• Trong trường hợp ngược lại ghi ra một dòng gồm chiều cao và trọng số của tháp đầy đủ có trọng số nhỏ nhất.

Sample Input

3 36

Sample Output

4 57

Subtask

• Có ~40\%~ số test ứng với ~40\%~ số điểm có ~a < b \leq a \times 10^8~.
• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~1 \leq a < b \leq 10^5~.
• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~1 \leq a < b \leq 10^{12}~.

Thành là một học sinh giỏi Toán. Vì vậy những kiến thức cơ bản trong toán học như tính giai thừa, tìm ước số, khai căn, ... đối với cậu là các bài toán dễ. Nhưng hôm nay Thành nhận được bài toán là "tìm ước số lớn nhất của ~\text{N!}~ sao cho căn bậc ba của nó là một số nguyên" và Thành cũng không phải mất nhiều thời gian để đưa ra kết quả. Để kiểm tra kết quả của Thành đưa ra có đúng hay không? Bạn hãy viết chương trình giải bài toán trên để so sánh với kết quả mà Thành đưa ra.

Input

Dòng đầu chứa số nguyên dương ~T ≤ 10~ (là số lượng bài toán);

~T~ dòng sau, mỗi dòng chứa một số nguyên dương ~N~ thể hiện câu hỏi tương ứng ~(N ≤ 10^5)~.

Output

Gồm ~T~ dòng, mỗi dòng là câu trả lời cho câu hỏi tương ứng. Vì kết quả có thể rất lớn nên các bạn chỉ cần đưa ra phần dư của nó khi chia cho ~10^9 + 7~.

Sample Input

2
1
4

Sample Output

1
8

Giải thích

Ta có ~T = 2~ (tương ứng với 2 bài toán):

Bài toán ~1~ có giá trị ~N = 1~: Vì ~1! = 1~ nên ước số lớn nhất có căn bậc ba là số nguyên cũng bằng ~1~.

Bài toán ~2~ có giá trị ~N = 4~: Vì ~4! = 24~. Trong các ước số của ~24~ thì số ~8~ là ước số lớn nhất có căn bậc ba là số nguyên (căn bậc ba của ~8~ bằng ~2~).

Subtask

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~1 < N ≤ 20~;

• Có ~40\%~ số test ứng với ~40\%~ số điểm với các trường hợp còn lại.

Cho một xâu ký tự ~S~ chỉ gồm các chữ cái la tinh in thường từ ~a~, ..., ~z~. Một xâu con ~X~ (gồm các ký tự ở vị trí liên tiếp) của S được gọi là một xâu có tần số xuất hiện cao nếu trong xâu ~X~ có một ký tự bất kỳ nào đó mà số lần xuất hiện của ký tự đó nhiều hơn tổng số lần xuất hiện của các ký tự còn lại trong ~X~.

Ví dụ:

• Với ~S =~ abbbabced, xâu con ~X =~ abbbabc là một xâu con tần số xuất hiện cao, vì ký tự ~b~ xuất hiện ~4~ lần, tổng số lần xuất hiện các ký tự còn lại bằng ~3~ (~a~ xuất hiện ~2~ lần, ~c~ xuất hiện ~1~ lần).

Nếu ~X =~ abbbabce, ký tự ~b~ xuất hiện nhiều lần nhất là ~4~ lần và tổng số lần xuất hiện của các ký tự còn lại cũng bằng ~4~ (~a~ xuất hiện ~2~ lần, ~c~ xuất hiện ~1~ lần, ~e~ xuất hiện ~1~ lần). Do vậy, ~X =~ abbbabce không phải là một xâu con tần số xuất hiện cao.

Yêu cầu: Tìm xâu con ~X~ (gồm các ký tự ở vị trí liên tiếp) của ~S~ là một xâu có tần số xuất hiện cao và có độ dài lớn nhất.

Input

Gồm một xâu ~S~ chỉ gồm các ký tự chữ cái la tinh in thường và có độ dài không lớn hơn ~2 \times 10^5~.

Output

Một số nguyên duy nhất là độ dài của xâu ~X~ tìm được.

Sample Input

aaa
ababb

Sample Output

3
5

Giải thích

Với aaa: ta có thể chọn xâu ~X~ thỏa mãn là aaa (ký tự ~a~ chiếm toàn bộ).

Với ababb: ta có thể chọn ~X =~ ababa vì ký tự ~a~ xuất hiện ~3~ lần, số ký tự còn lại là ~2~, hoặc ~X =~ babab vì ký tự ~b~ xuất hiện ~3~ lần, số ký tự còn lại là ~2~. Độ dài lớn nhất là ~5~.

Subtask

Có ~30\%~ số test ứng với ~30\%~ số điểm thỏa mãn: xâu ~S~ chỉ gồm các ký tự thuộc tập ~{a, b, c}~ và có độ dài ~\le 2 \times 10^3~.

Có ~30\%~ số test ứng với ~30\%~ số điểm thỏa mãn: xâu ~S~ chỉ gồm các ký tự chữ cái la tinh in thường và có độ dài ~\le 10^4~.

Có ~40\%~ số test ứng với ~40\%~ số điểm còn lại: xâu ~S~ chỉ gồm các ký tự chữ cái la tinh in thường và có độ dài ~\le 2 \times 10^5~.