An bydrocarbon is an organic compound which contains only carbons and hydrogens. An isomer is a compound that has the same number of carbons but different structures. Heptane, for example, is a hydrocarbon with 7 carbons. It has nine isomers. The structural formula of three are shown in Figure 1. Carbons are represented by the letter C, and bonds between carbons are represented by a straight line. In all figures, hydrogens are not represented for simplicity. Each carbon can be connected to a maximum of 4 carbons.

<image>
---
Figure 1: These three examples of isomers of heptane have the same number of carbons but different structures.
---



Let define a chain in an isomer as a sequence of connected carbons without branches. An isomer can have many chains of the same length. Figure 2 shows the longest chain of carbons for each of the represented isomer. Note that there can be many instances of longest chain in an isomer.

<image>
---
Figure 2: The figures shows one instance of longest chain of carbons in each isomer. The first and the second isomers show longest chains of 5 carbons. The longest chain in the third isomer has 4 carbons.
---



Your task is to identify the number of carbons of the largest possible carbon compound whose longest carbon chain has n (1 ≤ n ≤ 30) carbons.



Input

Each input contains a list of number of carbons, i.e. the length of a carbon chain.

The number of input lines is less than or equal to 30.

Output

For each number n in input, identify the number of carbons of the largest possible carbon compound whose longest carbon chain has n carbons.

Example

Input

1
4


Output

1
8
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){

	int d[31];
	d[2]=0;
	d[3]=1;
	for(int i = 4; i < 31; i++){
		d[i]=d[i-1]+(int)pow(3.0,i-3);
	}

	int n;
	while(cin>>n){
		if(n==1)
			cout<<1<<endl;
		else if(n==2)
			cout<<2<<endl;
		else if(n==3)
			cout<<5<<endl;
		else if(n==4)
			cout<<8<<endl;
		else if(n%2==1){
			int t=((n)/2);
			int sum=0;
			while(t>=2){
				if(t==n/2){
					int m = d[t];
					if(m!=0){
						sum += (2*(m+pow(3.0,t-3)*4*3))+1;
					}
					else{
						sum+=8+1;
					}
				}
				else{
					int m=d[t];
					if(m!=0)
						sum+=((2*(m+pow(3.0,t-3)*4*3))+1)*2;
					else
						sum+=(8+1)*2;
				}
				t--;
			}
			cout<<sum+2*4<<endl;
		}
		else{
			int t=((n-1)/2);
			int sum=0;
			while(t>=2){
				int m=d[t];
				if(m!=0)
					sum+=((2*(m+pow(3.0,t-3)*4*3))+1)*2;
				else
					sum+=(8+1)*2;
				t--;
			}
			cout<<sum+2*4<<endl;
		}
	}

	return 0;
}