Với mỗi số nguyên ~X~ trong đoạn ~[L, R]~, tìm ước nguyên tố lớn nhất của ~X~ và tính tổng của chúng.

Ví dụ với ~[L, R]~ = ~[2, 6]~, ta có kết quả là: ~2 + 3 + 2 + 5 + 3 = 15~.

Đầu vào

Dòng đầu tiên chứa một số nguyên ~T~ là số lượng bộ test ~(1 \le T \le 10^6)~.

~T~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~L, R~ ~(2 \le L \le R \le 10^6)~

Đầu ra

Với mỗi test, in ra kết quả trên một dòng.

Ví dụ