Problem Description

　　

　　
　　上图是一棵Stern-Brocot树，其生成规则如下：
　　从第1行到第n行，每行相邻两数a/b和c/d，产生中间数(a+c)/(b+d)，置于下一行中。将一行的分数（包括0/1,1/0），进行约分简化，则每一行（包括0/1,1/0,1/1），不会出现两个相同的分数。若分子或者分母大于n，则去掉该分数，将剩下的分数，从小到大排序，得到数列F。
　　现在请您编程计算第n行的数列F的个数。

Input

　　输入包含多组测试用例，每组输入数据是一个正整数n（n<=1000000）。

Output

　　对于每组的测试数据n，请输出第n行的数列F的个数。

1
2
4
6

3
5
13
25