“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

Giới hạn:

Subtask 1: 1 ≤ 𝑎, 𝑏 ≤ 200, 𝑇 ≤ 100 ( 20% 𝑡𝑒𝑠𝑡)

Subtask 2: 1 ≤ 𝑎, 𝑏 ≤ 2000, 𝑇 ≤ 1000 ( 20 % 𝑡𝑒𝑠𝑡)

Subtask 3: 1 ≤ 𝑎, 𝑏 ≤ 10⁶ , 𝑇 ≤ 1000 ( 20% 𝑡𝑒𝑠𝑡)

Subtask 4: 1 ≤ 𝑎, 𝑏 ≤ 10⁶ , 𝑇 ≤ 10⁵( 20 % 𝑡𝑒𝑠𝑡)

Subtask 5: 1 ≤ 𝑎, 𝑏 ≤ 10¹² , 𝑇 ≤ 10⁵  ( 20 % 𝑡𝑒𝑠𝑡)

Lưu ý: số lượng ước phải là số nguyên tố lớn hơn 2 với trường hợp số đó lớn hơn 10⁶