上图是一棵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的个数。
Sample Input
1
2
4
6
Sample Output
3
5
13
25
/*
可以看到,如果把右半边的数字变成他们的倒数,整个树是关于中间那列对称的.
还有一个性质就是同一行的数字是递增的,这一点很容易得到证明
既然是对称的,只要考虑左半边就行(从0到1),一整行的结果就是半行的结果*2-1
还有一条性质:数字的分子和分母是互质的,同样很容易证明
*/
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<set>
#include<cstdlib>
#include<stack>
typedef long long LL;
const int maxsize = 1e6+7;
using namespace std;
LL Phi[maxsize];//Pri[i]表示i的欧拉函数
void makePhiTable1(int n)//nloglogn
{
int i;
for(i=1;i<=n;i++) Phi[i] = i;
//单独的欧拉函数求法Pri[n] = n*(1-1/p1)*(1-1/p2)*(1-1/p3)....
//其中p1,p2,p3是n的素数因子
for(i = 2;i<=n;i+=2) Phi[i]/=2;//之所以使用这一步是因为下面有一个循环会穷举所有的因子
for(i=3;i<=n;i++)
{
if(Phi[i]==i)//说明在i增长到这个i之前,他不是任何之前i的整数倍,所以他是一个素数,所以可以用它来构造以他为因数的欧拉函数
{
for(int j=i;j<=n;j+=i)
Phi[j] = Phi[j]/i*(i-1);
}
}
}
LL getPhi(LL x)//logn
{
LL i,ret = x;
for(i=2;i<sqrt(1.0*x)+1;i++)//sqrt(x)渐渐减小
{
if(x%i==0)
{
ret = ret/i*(i-1);
while(x%i==0) x/=i;//循环的次数实际上是这个素数因子的质数
}
}
if(x>1) ret = ret/x*(x-1);//如果x>1,那么说明x是一个素数
return ret;
}
LL F[maxsize];
void init(int n)
{
makePhiTable1((int)1e6+1);
F[1] = 2;
F[2] = 3;
for(int i = 3 ;i<=n;i++)
{
F[i] = F[i-1] + Phi[i];
}
}
int main()
{
//freopen("finput.txt","r",stdin);
LL n;
init(1000000);
//cout<<Phi[88888]<<endl;
while(~scanf("%lld",&n))
{
printf("%lld\n",2*F[n]-1);
}
return 0;
}
