Bí mật quốc gia

Gerald bán bí mật quốc gia, mỗi bí mật có giá $n$ mark. Quốc gia nơi Gerald bán bí mật không có tiền giấy, chỉ có tiền xu mệnh giá là lũy thừa của $3$: $1,3,9,27,\dots$ mark — không có mệnh giá nào khác.

Một khách hàng đến mua bí mật nhưng không có tổ hợp tiền xu nào trả đúng $n$ mark. Khi đó, anh ta sẽ lấy ra tất cả các đồng xu của mình và cố trả một số tiền lớn hơn hoặc bằng $n$ với số đồng xu ít nhất có thể.

Trong tất cả các tổ hợp đồng xu mà người mua không thể trả đúng $n$ mark, hãy tìm tổ hợp khiến số đồng xu tối thiểu cần dùng để trả ít nhất $n$ mark là lớn nhất. Hãy in ra giá trị lớn nhất đó.

Dữ liệu vào

Một số nguyên duy nhất $n$.

Dữ liệu ra

Một số nguyên — số đồng xu nhiều nhất mà người mua không may có thể phải dùng.

Ràng buộc

• $1\le n\le {10}^{17}$

Ví dụ