Số đặc biệt

Trong giờ học môn Toán, thầy giáo đưa ra quy ước "Số đặc biệt" là số nguyên dương có đúng \(4\) ước số dương.

Ví dụ: \(8\) có \(4\) ước số dương gồm \(1, 2, 4, 8\) nên \(8\) được gọi là số đặc biệt; \(25\) có \(3\) ước số dương gồm \(1, 5, 25\) nên \(25\) không phải là số đặc biệt.

Thầy giáo cho mỗi bạn hai số nguyên dương \(L, R\) \((1 \le L < R \le 10^6)\). Yêu cầu mỗi bạn đếm số lượng số đặc biệt trong đoạn \([L, R]\).

Yêu cầu. Hãy lập trình giúp các bạn đếm số lượng các số đặc biệt trong đoạn \([L, R]\).

Input

• Dòng thứ nhất ghi số nguyên dương \(T\) \((T \le 10^6)\) là số lượng cặp số nguyên dương \(L, R\);

• \(T\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(L, R\).

Output

Ghi ra \(T\) dòng, mỗi dòng ghi số lượng các số đặc biệt trong đoạn \([L, R]\) tương ứng.

Notes

• Từ \(6\) đến \(9\) có \(2\) số đặc biệt là \(6\) và \(8\).

• Từ \(10\) đến \(15\) có \(3\) số đặc biệt là \(10\), \(14\), \(15\).

• Từ \(20\) đến \(33\) có \(5\) số đặc biệt là \(21\), \(22\), \(26\), \(27\), \(33\).

Scoring

• (\(60\%\)) \(T \le 10^2\), \(R \le 10^3\);

• (\(30\%\)) \(10^2 < T \le 10^3\), \(R \le 10^5\);

• (\(10\%\)) \(10^3 < T \le 10^6\), \(R \le 10^6\).