Hai người chơi một trò chơi. Ban đầu người 1 chọn số nguyên dương ~n~ và đưa cho người 2. Người 2 thực hiện lặp lại các bước:

• Chọn một số nguyên dương ~x > 1~ sao cho ~n~ chia hết cho ~x~.
• Thay ~n~ bằng ~n / x~.

Khi ~n = 1~ và không còn nước đi hợp lệ, trò chơi kết thúc. Điểm của người chơi là số lần đã thực hiện bước trên.

Để tăng phần thú vị, người 1 chọn ~n~ có dạng ~\frac{a!}{b!}~ với ~a, b~ là số nguyên dương và ~a ≥ b~. Ở đây ~k!~ là tích của các số nguyên dương không vượt quá ~k~.

Yêu cầu: Với mỗi cặp ~(a, b)~, hãy tính số điểm tối đa có thể đạt được.

Input ~divgame.inp~

• Dòng 1: số nguyên dương ~t~ — số test ~(1 ≤ t ≤ 10^6)~.
• ~t~ dòng tiếp theo: mỗi dòng chứa cặp ~a, b~ ~(1 ≤ b ≤ a ≤ 5·10^6)~, biểu diễn ~n = \frac{a!}{b!}~.

Output ~divgame.out~

• Gồm ~t~ dòng, mỗi dòng in ra số điểm tối đa tương ứng test đó.

Ví dụ

divgame.inp

2
3 1
6 3

divgame.out

2
5

Giải thích:

• Với ~(a, b) = (3, 1)~: ~n = \frac{3!}{1!} = 6 = 2 · 3~. Có thể chia lần lượt cho ~2~, rồi ~3~ → tối đa 2 bước.
• Với ~(6, 3)~: ~n = \frac{6!}{3!} = 4 · 5 · 6 = 120 = 2^3·3·5~, tổng mũ nguyên tố là ~3 + 1 + 1 = 5~ → 5 bước.

Ràng buộc chấm điểm

• Subtask 1 (30%): ~1 ≤ b ≤ a ≤ 15~,
• Subtask 2 (30%): ~t = 1~,
• Subtask 3 (20%): ~1 ≤ b ≤ a ≤ 10^5~,
• Subtask 4 (20%): không ràng buộc thêm.