题目描述

有一位旅行者去找商人买了一个价值 $n$ 元的东西。在结账时，他突然尴尬地发现自己身上只有硬币了，并且他无法付给商人刚好 $n$ 元钱。旅行者随身带着的硬币的面值都是 $3$ 的整数次幂，这样的硬币面值可以很大，旅行者身上也有非常多，多到自己都数不清呢。

这个商人不喜欢找零，所以旅行者试图用数量尽可能少的硬币给他一笔大于等于 $n$ 的钱，并且额外付出的部分要最小。可是作为旅行者的忠实粉丝，商人好像认出了旅行者，并要求在上述情况下得到尽可能多的硬币用于收藏。

聪明的你可以帮帮他吗？请求出商人最多可以得到的硬币数量。

输入格式

一个整数 $n$，$1\le n\le 10^{17}$。

输出格式

一个整数表示答案。

1

1

4

2