Vì biết Nhật rất kém về số nguyên tố nên trong kì thi này của trường Newton, thầy Nam đã ra một bài toán hóc búa như sau: "Cho 2 số nguyên dương \(a, b\). Hãy tìm số lượng các số trong khoảng [\(a, b\)] sao cho số lượng ước của chúng là một số nguyên tố"

Không chỉ dừng lại đó, thầy Nam còn đánh đố Nhật bằng cách không chỉ cho một bộ \(a, b\) mà cho những \(T\) bộ số. Nhật rất cần qua kì thi này nên anh ấy nhờ đến các bạn lập trình chương trình để giải bài toán của thầy Nam.

Input

• Dòng đầu chứa số nguyên dương \(T\) là số bộ test
• \(T\) dòng sau mỗi dòng gồm 2 số nguyên dương \(a, b\)

Output

• \(T\) dòng, dòng thứ \(i\) là kết quả của bộ test thứ \(i\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \leq a,b \leq 200\), \(T \leq 100\)
• Subtask \(2\) (\(20\%\) số điểm): \(1 \leq a,b \leq 2000\), \(T \leq 1000\)
• Subtask \(3\) (\(20\%\) số điểm): \(1 \leq a,b \leq 10^6\), \(T \leq 1000\)
• Subtask \(4\) (\(20\%\) số điểm): \(1 \leq a,b \leq 10^6\), \(T \leq 10^5\)
• Subtask \(5\) (\(20\%\) số điểm): \(10^6 < a,b \leq 10^{12}\), \(T \leq 10^5\) và số lượng ước phải là số nguyên tố lớn hơn \(2\)

Example

5
12 400
412 1000
32 100
1910 3000
1 100    

82
93
17
141
32