Description

给你一个n，将其按照递增顺序排成序列123……n，然后在他们之间加入加号、减号或什么也不加。分别使它们做加法、减法或将数字合并。求最终结果为0的式子个数。1

Input

每行给出一个n(n>=1,n<=9)，输入到文件结束。

Output

对于每个n，输出满足要求的式子个数。每个结果占一行。

Sample

Input

1
2
3

Output

0
0
1

Hint

n为1、2时，没有满足要求的式子，所以结果为0。 n为3时，有一个式子1+2-3=0，满足要求;其它的如12-3!=0， 1-23!=0等都不满足要求，所以结果为1。