Một số được coi là bất thường nếu tổng các chữ số và tổng bình phương các chữ số (trong hệ thập phân) của nó nguyên tố cùng nhau.

Ví dụ: số \(23\) (tổng các chữ số là \(2+3=5\), tổng bình phương các chữ số là \(2^2+3^2=13\), \(gcd(5, 13)=1\)) và số \(41\) (tổng các chữ số là \(4+1=5\), tổng bình phương các chữ số là \(4^2+1^2=17\), \(gcd(5, 17)=1\)) là các số bất thường.

Bờm rất thích thú với định nghĩa số bất thường này và Bờm muốn nhờ các bạn xác định số lượng số bất thường trong đoạn \([L, R]\).

Input

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

Output

• Một số nguyên duy nhất là số lượng số bất thường trong đoạn \([L, R]\).

Example

10 11

1

100 150

19

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1 \le L, R \le 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le L, R \le 10^9\).
• Subtask \(3\) (\(30\%\) số điểm): \(1 \le L, R \le 10^{18}\).

Nguồn: CĐ DHBB 2020