"Cho 2 số nguyên dương a, b. Hãy tìm số lượng các số trong khoảng [a, b] (a < b)sao cho số lượng ước của chúng là một số nguyên tố". Bên cạnh đó,không chỉ cho một bộ a, b mà cho T bộ số a, b.

Input

• Dòng 1 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 \le a, b \le 200, T \le 100~.
• Subtask ~2~ (~20\%~ số điểm): ~1 \le a, b \le 2000, T \le 1000~.
• Subtask ~3~ (~20\%~ số điểm): ~1 \le a, b \le 10^6, T \le 1000~
• Subtask ~4~ (~20\%~ số điểm): ~1 \le a, b \le 10^6, T \le 10^5~
• Subtask ~5~ (~20\%~ số điểm): ~1 \le a, b \le 10^{12}, T \le 10^5~

Ví dụ

Input

5
12 400
412 1000
32 100
1910 3000
1 100

Output

82
93
17
141
32