Hương có một trò chơi với những con số. Cô ấy viết một số nguyên dương lên bảng, rồi tính tích các chữ số của nó. Ví dụ, với số \(36\), tích các chữ số là \(3 \times 6 = 18\).

Hương muốn đếm xem trong đoạn \([L, R]\) có bao nhiêu số mà tích các chữ số của nó không vượt quá \(K\).

Input

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

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 30 10
Output:
16

Giải thích: Các số thỏa mãn là \(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,20\).

Ví dụ 2

Input:
10 50 5
Output:
11

Subtask