Một số được gọi là siêu nguyên tố nếu nó có đúng 3 ước.

Yêu cầu: Cho hai số nguyên \(L,R\). Đếm số lượng các số siêu nguyên tố trong đoạn \([L,R].\)

Input

• Dòng đầu tiên chứa số nguyên \(T (1≤T≤100) \)là số bộ test.

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L,R(L≤R≤10^{12} ).\)

Output

• Gồm \(T\) dòng, mỗi dòng ghi số lượng các số siêu nguyên tố trong đoạn \([L,R]\) ứng với test tương ứng.

Sample Input

1
1 10

Sample Output

2