参考资料：
[1]:https://www.2cto.com/kf/201308/233613.html
题意，题解在上述参考资料中已经介绍的非常详细了，接下来的内容只是记录一下我的理解；
我的学习记录：
定义 f(x) : x的因子个数；
φ(x) : x之前与x互素的数的个数；
那么 F(x) = x - f(x) - φ(x) + 1;
为什么要 +1 呢？
因为 f(x) 和 φ(x) 同时包含 1 这个数，所以要加上多减去的 1；
根据算术基本定理：
任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
N=P1a1×P2a2×P3a3×......×Pnan，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。
那么，N的因子肯等为 x = P1b1×P2b2×P3b3×......×Pnbn 这种形式，易知 b1∈[0,a1] , b2∈[0,a2] , ..... , bn∈[0,an]，共
f(x) = (a1+1)*(a2+1)*........*(an+1)个因子；
如果要使 f(N) 为奇数，那么 (a1+1),(a2+1),........,(an+1) 要全部为奇数，也就是说 a1 , a2 ,........,an 全为偶数，即 N 为完全平方数；
综上：
N为完全平方数时，f(N)为奇数；
N为非完全平方数时，f(N)为偶数；
接下俩就是求解φ(x)，这个是数论中比较重要的公式--欧拉公式；
定理1：
如果GCD(a,b) == 1，那么 φ(a*b) = φ(a)*φ(b);
定理2：
如果 p 为素数，那么 φ(pk) = pk-1*(p-1);
（相关证明自行百度，逃）；
定理3：
那么对于任意大于 2 的数 x = P1a1×P2a2×P3a3×......×Pnan， φ(x) 为偶数；
①如果p为奇数：
根据公式 φ(p^k)=p^(k-)*(p-)
(p-)一定为偶数，则 φ(p^k)为偶数，则 φ(x)为偶数；
②如果p为偶数：
那么，p只能为2；
如果k > ，那么 φ(^k)为偶数；
如果k = ，那么对于大于2的数x，一定会分解出除2的另一个质因子p2，
根据①的得知φ(p2^k2)为偶数；
综上φ(x)为偶数；
定理3简单证明
综上所述：
当 x > 2 时：
①如果x为完全平方数，那么 F(x) = x - f(x) - ( φ(x) -1) = x - 奇数 - 奇数 = x - 偶数，只有当 x 为奇数时，F(x)为奇数；
②如果x为非完全平方数，那么 F(x) = x - f(x) - ( φ(x) -1) = x - 偶数 - 奇数 = x - 奇数，只有当 x 为偶数时，F(x)为奇数；
所以，[3,x] 中使得 F(i) 为奇数的个数 ⇔ [3,x]中 奇完全平方数+偶非完全平方数 = 偶数-偶完全平方数+奇完全平方数；
[3,x]中偶数的个数为 x/2 - 1 (减掉的是 2), 平方数个数为 sqrt(x)-1 (减掉的是 1)个;
如果 (sqrt(x)-1)%2 == 0（sqrt(x)为奇数），那么 偶完全平方数与奇完全平方数 个数相等，F(x) = x/2-1;
如果 (sqrt(x)-1)%2 ≠ 0（sqrt(x)为偶数），那么 偶完全平方数比奇完全平方数 个数多1，F(x) = x/2-1 -1;
AC代码：
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define ll long long ll n,m; ll Solve(ll x)
{
if(x < )
return ;
ll tot=sqrt(x);
if(tot*tot > x)//sqrt()函数存在精度问题，可能使得tot*tot > x
tot--;
ll ans=x/-;
return ans+((tot% == )?-:);
}
int main()
{
int test;
scanf("%d",&test);
while(test--)
{
scanf("%lld%lld",&n,&m);
printf("%lld\n",Solve(m)-Solve(n-));
}
return ;
}