Background

"Plus Ultra!"

Description

调味市陷入了危机——市中心竟然一夜之间出现了一棵巨大无比的西兰花树！可怕的流言在调味市传开了——这棵西兰花树会越长越大，最终吞噬整个城市！为了拯救城市，调味市长从某英雄学院招募了无数位英雄。但是如果全部英雄一起上场，过大的力量可能反而会摧毁城市，因此只能从中挑选部分英雄。调味市长经过调查，发现这些英雄的力量值分别为1,3,9,...,3^(i-1),...。如果他挑选了第1位和第2位英雄，就能得到1+3=4的力量值。他想算出能得到的第k小力量值是多少，以便进行挑选。

Format

Input

输入数据有多组。对每组数据，输入一行一个整数，为k，含义如题。保证数据组数不超过100组，1<=k<=2147483647。

Output

对每组数据，输出一个整数，占一行，表示第k小力量值。

Sample 1

Input

2
4

Output

3
9

Limitation

1s, 64MB for each test case.

Source

2019网宿杯XMU程序设计竞赛网络预赛第一场