Có hai sỹ quan chơi một trò chơi. Đầu tiên người thứ nhất đưa cho người thứ hai một số nguyên dương ~n~. Nhiệm vụ của người thứ hai là thực hiện nhiều vòng chơi nhất có thể. Mỗi vòng chơi, anh ta chọn ra một số nguyên ~x > 1~ sao cho ~n~ chia hết cho ~x~ và thay thế ~n~ bởi ~\dfrac{n}{x}~. Khi ~n~ bằng ~1~ thì trò chơi kết thúc và điểm mà người chơi nhận được là số lần lấy được số ~x~.

Để trò chơi trở nên thú vị hơn, số ~n~ được chọn có dạng ~\dfrac{a!}{b!}~ với hai số nguyên dương ~a, b\ (a > b)~. Ở đây ~k! = 1 \times 2 \times \dots \times k~.

Yêu cầu: Hãy xác định số điểm lớn nhất mà người thứ hai nhận được.

Input:

Vào từ file văn bản NGAME.INP gồm:

• Dòng đầu tiên ghi số nguyên dương ~t\ (1 ≤ t ≤10^6)~ là số lần chơi
• ~t~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~a, b\ (1≤b≤a≤5\times 10^6)~ mô tả dạng của số ~n~ trong ván chơi.

Output:

Ghi ra file văn bản NGAME.OUT: Với mỗi lân chơi in ra số điểm lớn nhất nhận được

Ghi chú:

• Subtask 1 (50%): ~1 ≤ b ≤ a ≤ 14;\ T ≤ 10~
• Subatsk 2 (50%): ~20 ≤ b ≤ a ≤ 5\times 10^6;\ T ≤ 10^6~

Ví dụ:

NGAME.INP

2
3 1
6 3

NGAME.OUT

2
5