Description

RZX是个狂热的热火队球迷，尤其喜欢勒布朗詹姆斯，由于篮球小皇帝简称LBJ，所以RZX特别喜欢LBJ这三个字母，现在RZX拿到一LBJ的巨幅海报，他就有了涂鸦的兴趣，已知海报长为n,RZX打算在每单位长度上上涂上L,B,J中的其中一个字母，但是RZX在家中深怕姐姐，所以她不愿意看到两个J相邻，这会勾起他无尽的悲惨回忆，现在你的任务是计算给定长为n的海报,RZX共有多少种涂鸦的方法。

Input

输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0<n<40)。

Output

对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample

Input

1
2

Output

3
8

Source: 琐利达尔