Vào một ngày đẹp trời, khi ánh nắng nhẹ chiếu qua từng tán lá, bgb đang thong thả đi dạo trong khu vườn quen thuộc của mình. Không khí yên bình khiến bgb cảm thấy vô cùng thư giãn và thầm nghĩ trên đời sao lại có nhiều người ảo tưởng vậy nhỉ?
Nhưng vừa nói xong, một cơn gió lạnh thổi qua.
Phía sau bụi cây, có một người lạ xuất hiện. Tên đó tự xưng tên là hieuln2011.
Chưa kịp hiểu chuyện gì xảy ra, bgb đã bị bắt vào một không gian tối tăm, xung quanh là những bức tường phủ kín bởi vô số con số kỳ lạ.
hieuln2011 cười lớn và nói:

• "Ngươi dám cười ta là kẻ ảo tưởng? Vậy hôm nay ta sẽ cho ngươi thấy thế nào là ảo tưởng thật sự!"

Nó đưa ra thử thách:

Ta sẽ cho ngươi một số \(n\).

Nhiệm vụ của người là tìm số lượng số \(x\) là số ảo tưởng thoả mãn \(1 ≤ x ≤ n\), \(x\) là số ảo tưởng nếu \(x\) thoả mãn 2 điều kiện:

• Tổng các chữ số chia hết cho số lượng chữ số
• Tích các chữ số chia hết cho tổng các chữ số

Yêu cầu: Nhập vào một số nguyên dương \(n\). Hãy tính số lượng số ảo tưởng từ \(1\) đến \(n\).

Input

• Một dòng duy nhất chứa số nguyên \(n\) \((1 ≤ n ≤ 10^{12})\)

Output

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

Example

20

10

Scoring

• Subtask 1 \(20\%\) số test tương ứng với \(20\%\) điểm có \(1 ≤ n ≤ 100\).
• Subtask 2 \(30\%\) số test tương ứng với \(30\%\) điểm có \(1 ≤ n ≤ 10^5\).
• Subtask 3 \(50\%\) test còn lại ứng với \(50\%\) số điểm có \(1 ≤ n ≤ 10^{12}\).