Description

对于一个有N个点的无向图(无重边,无自环),我们定义删点游戏的规则:

有一个计数器从0开始计数,1,2,3...一直到N-1.计数器显示数字为i时,删掉图中度数为i的节点,并且和它相连的边也一起删掉.游戏结束时,图中可能还会有一些点.

现在让你编程计算这样的删点游戏,对于有N个点的无向图,最后最多可能剩下几个节点.

Input

多组数据,每组数据包括一个N(1<=N<=16)

Output

输出最多剩下多少个节点

Sample

Input

1
2

Output

0
0

Source: zjut_DD