Cho ~n~ là số nguyên dương. Số nguyên ~m~ là tổng của ~n~ với các chữ số của nó. ~n~ được gọi là nguồn của ~m~.

Ví dụ, ~n = 245~, khi đó ~m = 245 + 2 + 4 + 5 = 256~. Như vậy nguồn của ~256~ là ~245~.

Có những số không có nguồn và có số lại có nhiều nguồn. Ví dụ, số ~216~ có ~2~ nguồn là ~198~ và ~207~.

Yêu cầu: Cho số nguyên dương ~m~ (~m \le 10^{100}~) hãy tìm nguồn nhỏ nhất của nó, nếu không có ghi ra số 0.

INPUT

Chứa duy nhất số ~m~.

OUTPUT

Chứa số ~n~ tìm được, nếu không có số nguồn ghi ra số 0.

SAMPLE INPUT

216

SAMPLE OUTPUT

198

Trong lớp học toán ngày hôm nay của Cirno, cô ra một bài toán cho các học sinh của mình:

Cho một số nguyên dương, hãy đếm số cách xóa bỏ một chữ số (số còn lại có thể có số 0 ở đầu) để số còn lại chia hết cho 3, nhưng không chia hết cho 9 (vì cô không thích số 9).

Input:

• Một số nguyên dương ~n \le 10^{100000}~.

Output

• Số cách xóa thỏa mãn.

Sample Test

Input:

396

Output:

2

Giới hạn

• 60% số điểm: ~n \le 10^{1000}~
• 40% số điểm: Không có giới hạn gì thêm.