Có bao nhiêu số từ \(A\) đến \(B\) mà tổng các chữ số của nó là số nguyên tố.

Input

• Hai số $A, B\ (0

Cho số \(n\ (1≤ n ≤ 10^{10000})\). Tìm số lượng số không âm nhỏ hơn \(n\), có tổng bình phương các chữ số của nó chia hết cho 3.

Input

• Số \(n\)

Output

• Số lượng số tìm được. Chỉ ghi ra số dư của kết quả chia cho \(10^9+7\).

Input

9

Output

3

Input

10

Output

4

Input

15

Output

4

Nguồn: https://www.spoj.com/problems/SQAMOD/

Một số nguyên chia hết cho 3 thì tổng các chữ số của nó cũng chia hết cho 3.

Ví dụ: \(3702\ ⋮\ 3\) và \(3+7+0+2 = 12\ ⋮\ 3\).

Tính chất này cũng đúng đối với số 9.

Trong bài toán này, chúng ta sẽ dùng tính chất đó cho các số nguyên khác.

Input

• Ba số nguyên dương \(A, B\) và \(K\) (\(1 ≤ A ≤ B < 2^{31}\) và \(0 < K < 100\)).

Output

• Số lượng số nguyên trong phạm vi từ \(A\) đến \(B\) mà chia hết cho \(K\), đồng thời, tổng các chữ số của nó cũng chia hết cho \(K\).

Input

1 20 2

Output

5

Input

1 1000 4

Output

64

Nguồn: http://lightoj.com/volume_showproblem.php?problem=1068 / https://toph.co/p/m-beautiful-numbers

Số Ra-One là số mà hiệu của tổng các chữ số ở vị trí chẵn và tổng các chữ số ở vị trí lẻ là bằng 1.

Ví dụ số \(234563\) là số \(Ra-One\), vì \((2+4+6) - (3+5+3) = 1\).

Còn số \(123456\) không phải số \(Ra-One\), vì \((1+3+5) - (2+4+6) = -4 ≠ 1\)

Tìm số lượng số \(Ra-One\) từ \(A\) đến \(B\).

Input

• Hai số \(A, B\).

Output

• Số lượng số Ra-One tìm được.

Input

1 10

Output

1

Input

10 100

Output

9

Giải thích:

• VD1: Chỉ có 1 số \(Ra-One\) duy nhất là \(10\)
• VD2: Các số \(Ra-One\) là \(10, 21, 32, 43, 54, 65, 76, 87, 98\).

Giới hạn: \(1 ≤ A≤ B≤ 10^8\).

Nguồn: https://www.spoj.com/problems/RAONE

Một số là Lucifer nếu hiệu giữa tổng các chữ số ở vị trí chẵn và tổng các chữ số ở vị trí lẻ là một số nguyên tố.

Ví dụ số \(20314210\) là số Lucifer. Vì \((1+4+3+2)-(0+2+1+0)=10-3 = 7\) là số nguyên tố.

Tìm số lượng số Lucifer trong phạm vi từ \(A\) đến \(B\).

Input

• Hai số nguyên \(A,B\).

Output

• Số lượng số Lucifer trong phạm vi từ \(A\) đến \(B\).

Input

50 100

Output

18

Input

100 150

Output

3

Input

150 200

Output

16

Giới hạn: \(1 ≤ A≤ B≤ 10^9\).

Nguồn: https://www.spoj.com/problems/LUCIFER/

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\), số \(41\) 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

• Hai số nguyên \(L\) và \(R\) (\(1≤ L, R≤ 10^{18}\)).

Output

• Một số nguyên là kết quả cần tìm.

Input

10 11

Output

1

Input

100 150

Output

19

Giới hạn:

• Subtask 1 (40%): \(1≤ L, R ≤ 10^6\)
• Subtask 2 (30%): \(1≤ L, R≤10^9\)
• Subtask 3 (30%): \(1≤ L, R≤10^{18}\)

Nguồn: CĐ DHBB 2020

Love is a zigzag.

Tình yêu cũng giống như CF rating, có lúc lên lúc xuống. Một ngày buồn, Ami ngồi viết ra những con số vô thức. Khi nhìn lại, cậu nhận ra những con số vừa viết tạo thành một dãy số như nói hộ lòng mình. Những chữ số thay nhau tăng giảm, cứ tăng rồi lại giảm, cứ giảm rồi lại tăng. Cậu liền nghĩ ra một bài toán khá thú vị để đố đệ tử CaiWinDao.

Ami định nghĩa một số như cậu vừa viết là một Girl Number (?) nếu những chữ số của nó thay nhau tăng giảm liên tục. Cụ thể, a1a2...an là một Girl Number nếu:

\(a_1 < a_2 ; a_2 > a_3 ; a_3 < a_4 ; ...\) hoặc \(a_1 > a_2 ; a2 < a_3 ; a_3 > a_4 ; ...\)

Ami "nhờ" CaiWinDao đếm xem trong các số tự nhiên từ \(L\) đến \(R\), có bao nhiêu Girl Number? Vì CaiWinDao bí mất rồi :((, nên cậu ấy đành nhờ các bạn vậy!!!

Dữ liệu

• Dòng đầu chứa 2 số nguyên dương \(a, b\) (\(1 \le a, b \le 100000\)) tương ứng là số chữ số của \(L\) và \(R\).
• Dòng thứ hai chứa 2 số tự nhiên \(L, R\) (\(0 \le L \le R \le 10^{100000}\)).

Kết quả

• In ra số lượng Girl Number trong đoạn từ \(L\) đến \(R\). Vì đáp số có thể hơi lớn nên các bạn chỉ cần in ra số dư của đáp số khi cho \(10^9+7\).

Input

1 2
8 15

Output

7

Input

4 4
1998 2004

Output

0

Giải thích

• Ở ví dụ 1 , các số từ 8 đến 15 đều là Girl Number trừ 11.
• Ở ví dụ 2 , các số từ 1998 đến 2004 có 2 chữ số ở giữa bằng nhau nên không số nào thỏa mãn.

Nguồn: http://lequydon.ntucoder.net/Problem/Details/5841/

Cho hai số nguyên \(L\) và \(R\), yêu cầu tính xem trong đoạn \([L,R]\) có bao nhiêu số thỏa mãn:

• Không có các chữ số 0 vô nghĩa ở đầu
• Các chữ số của số đó hoàn toàn phân biệt.

Input

• Hai số $L, R\ (0

Xác định số lượng số nguyên từ \(A\) đến \(A\) thoả mãn các điều kiện

• Tổng của các chữ số là số nguyên tố
• Chia hết cho \(K\)

Input

• Hai số $A, B, K\ (0

Cho 2 số nguyên dương \(A, B\ (A≤ B)\). Tính tổng các chữ số có mặt trong các số nguyên từ \(A\) đến \(B\).

Input

• Hai số $A, B\ (0

Nhà Vũ trồng rất nhiều cây táo trong vườn. Những cây táo được trồng thành hàng và đánh số bắt đầu từ 1. Có một điều kì lạ là số táo trên cây sẽ tương ứng với số thứ tự được đánh trên cây đó như sau:

• Để tính số quả của cây táo thứ \(i\). Ta tách \(i\) thành những nhóm có chữ số liên tiếp bằng nhau. Với mỗi nhóm ta nhân chữ số đó với bình phương độ dài của nhóm. Tổng của tất cả các nhóm sẽ là số táo trên thứ \(i\). Ví dụ: cây thứ 77744007, sẽ có \(4\) nhóm 777,44,00777,44,00 và 77. Do đó số táo trên cây này là \(7 * 3^2+4*2^2+0*2^2+7*1^2=86\).

Input

• Dòng đầu gồm 2 số a và b (\(1 \leq a \leq b \leq 10^{15}\)).

Output

• In ra một số duy nhất là số táo mà Vũ được ăn.

Example

100 111

68

Điểm “bán hoàn hảo” của một số nguyên dương \(N\) là tích các chữ số của nó. Ví dụ, \(N = 1416\), điểm “bán hoàn hảo” của số nguyên dương \(N\) là \(1 \times 4 \times 1 \times 6 = 24\). Điểm “hoàn hảo” của một số nguyên dương \(N\) là tích của \(N\) với điểm “bán hoàn hảo” của nó. Ví dụ, \(N = 1416\), điểm “hoàn hảo” của số nguyên dương \(N\) là \(1416 \times 24 = 33984\).

Cho hai số nguyên dương \(A\) và \(B\), bạn hãy đếm số lượng số nguyên dương mà có điểm “hoàn hảo” nằm trong đoạn \([A,B]\).

Input

• Một dòng duy nhất chứa hai số nguyên dương \(A\) và \(B\) \((1 \leq A \leq B \leq 10^{18})\)

Output

• Một dòng duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(A,B \leq 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): \(A,B \leq 10^{10}\)
• Subtask \(3\) (\(30\%\) số điểm): \(A,B \leq 10^{14}\)
• Subtask \(4\) (\(30\%\) số điểm): \(A,B \leq 10^{18}\)

Example

10 50 

8

130 170 

3

Bạn được cho một số \(n\), hãy đếm số lượng số tự nhiên đối xứng có độ dài \(2n+1\) có tổng các chữ số chia hết cho 10.

Input

• Dòng đầu tiên và duy nhất chứa một số nguyên \(n\)

Output

• In ra một số nguyên duy nhất là kết quả cần tìm.

Constraints

• \(n \leq 30\)

Example

1

9

http://lequydon.ntucoder.net/Problem/Details/6299

Một số được coi là số anh em 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ó là số nguyên tố. Ví dụ: số \(23\), số \(41\) là các số anh em.

Yêu cầu: Hãy xác định số lượng số anh em trong đoạn \([L,R]\).

Input: Đọc từ file văn bản ANHEM.INP gồm hai số nguyên \(L\) và \(R\) (\(1 <L, R \le 10^{18}\)).

Output: Ghi ra file văn bản ANHEM.OUT một số nguyên là kết quả cần tìm.

Scoring

• Subtask \(1: 40\%\) test có \(1 <L, R \le 10^6\).
• Subtask \(2: 30\%\) test có \(1 <L, R \le 10^9\).
• Subtask \(3: 30\%\) test có \(1 <L, R \le 10^{18}\)

Example

10 11

1

50 100

8