#P18597. Euclidean Algorithm

Euclidean Algorithm

Euclidean Algorithm

题目描述

考试时,你试图回想最大公约数的算法。你记得 gcd⁡(x,y)\gcd(x,y) 是同时整除 x,yx,y 的最大正整数,却忘记了课堂上的其他内容。模糊的记忆让你设计出如下算法。

最初黑板上写着两个正整数 x,yx,y。每一步可以选择两个已经写在黑板上的数 a,ba,b,计算

c=2a−b.c=2a-b.

仅当 c>0c>0 时,才可以把 cc 也写到黑板上,原有数字仍然保留。

对数对 (x,y)(x,y),你把经过任意多次操作(也可以不操作)能够写出的最小正整数,作为算法的结果。

例如,初始为 (10,14)(10,14) 时,先写出 2×10−14=62\times10-14=6,再写出 2×6−10=22\times6-10=2。可以证明无法写出 11,因此算法给出了正确的最大公约数。可是对 (10,16)(10,16),能得到的最小数是 44,真正的最大公约数却是 22。

给定 nn,求满足 1≤x<y≤n1\le x<y\le n 且上述算法的结果恰好为 gcd⁡(x,y)\gcd(x,y) 的数对 (x,y)(x,y) 的数量。

特别地,若 gcd⁡(x,y)=x\gcd(x,y)=x,也认为算法正确,因为 xx 最初就写在黑板上。

输入格式

第一行一个整数 zz,表示测试用例数。

接下来 zz 行,每行一个整数 nn,且 n≥2n\ge2。

数据范围

每个输入文件都属于以下三组之一:

输入组 测试用例数 每个测试用例的范围
第一组 1≤z≤30001\le z\le3000 2≤n≤1062\le n\le10^6
第二组 z=30z=30 2≤n≤1092\le n\le10^9
第三组 z=3z=3 2≤n≤10112\le n\le10^{11}

不能将这些限制合并为“任意 z≤3000z\le3000、任意 n≤1011n\le10^{11}”。

输出格式

对每个测试用例,输出一行一个整数,表示所求数对数量。

样例输入 1

3
2
5
14

样例输出 1

1
9
62