Cho \(t\) yêu cầu, với mỗi yêu cầu gồm \(2\) số nguyên \(l\), \(r\). Được biết số nguyên tố là số chỉ có \(2\) ước số là \(1\) và chính nó.

Yêu cầu

• Đếm số lượng số có tổng các chữ số là số nguyên tố từ \(l\) tới \(r\).

Dữ liệu

• Dòng đầu tiên, chứa số nguyên dương \(t\) là số lượng yêu cầu.
• \(t\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \(l\), \(r\).

Kết quả

• In ra \(t\) dòng, mỗi dòng in ra \(1\) số nguyên là số lượng số có tổng các chữ số là tố nguyên tố từ \(l\) tới \(r\).

Ràng buộc

• Subtask \(1\): \(25\%\) số test với \(t = 1\) và \(l, r \leq 2*10^6\)
• Subtask \(2\): \(25\%\) số test với \(t \leq 100\) và \(l, r \leq 2*10^6\)
• Subtask \(3\): \(50\%\) số test với \(t\) \(\leq\) \(100\) và \(l\), \(r\) \(\leq\) \(10^{18}\)

3
2 10
4 7
1 100

4
2
37