Tý cần giải bài toán sau:

Phương đang học về số nguyên tố. Cô ấy phát hiện ra rằng tổng bình phương các chữ số của một số cũng có thể là số nguyên tố. Ví dụ, với số \(12\), tổng bình phương các chữ số là \(1^2 + 2^2 = 5\), và \(5\) là số nguyên tố.

Cho hai số \(L, R\), hãy đếm xem trong đoạn \([L, R]\) có bao nhiêu số mà tổng bình phương các chữ số của nó là số nguyên tố.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Input

• Một dòng duy nhất chứa hai số nguyên \(L, R\) (\(0 \le L \le R \le 10^{18}\)).

Output

• Một số nguyên duy nhất là số lượng số thỏa mãn.

Ví dụ

Ví dụ 1

Input:
1 20
Output:
7

Giải thích: Các số thỏa mãn là \(1\) (\(1\)), \(2\) (\(4\)), \(4\) (\(16\)), \(5\) (\(25\)), \(6\) (\(36\)), \(7\) (\(49\)), \(10\) (\(1\)).

Ví dụ 2

Input:
50 100
Output:
14

Subtask