构造：结论题，gcy数竞大佬tql%%%orz。
结论
先放结论：如果 \(x \bmod 4=2\) ，那么 \(x\) 无法被表示为 \(a^2-b^2\) 的形式；除此之外的其他数都可以。
证明
对 \(a^2-b^2\) 因式分解，得 \(x=(a+b)(a-b)\) 。
当 \(x \bmod 2=1\) 时
包含 \(x \bmod 4=1\) 和 \(x \bmod 4=3\) 的情况。
尝试构造 ：
\[\begin{cases} x+y=n \\x-y=1\end{cases} \]解得：
\[\begin{cases} x=\frac{n+1}{2} \\y=\frac{n-1}{2}\end{cases} \]因为 \(x\) 为奇数，所以 \(x,y\) 皆为整数，成立。
当 \(x \bmod 4=0\) 时
把 \(4\) 提出来：
\[x=4t=(x+y)(x-y) \]所以设 \(x+y=2m,x-y=2k\) ，\(m,k\) 皆为整数 。
则解得
\[\begin{cases} x=m+k \\y=m-k\end{cases} \]显然 \(x,y\) 为整数，成立。
当 \(x \bmod 4=2\) 时
把 \(2\) 提出来：
\[x=2t=(x+y)(x-y) \]所以设 \(x+y=2m,x-y=k\) ，\(m,k\) 皆为奇数 。因为 \(2m\) 已经是偶数了，如果 \(k\) 还是偶数，那么就 \(x \bmod 4=0\)，与题设矛盾，不成立 。
则解得
\[\begin{cases} x=\frac{2m+k}{2}=m+\frac{k}{2} \\y=\frac{2m-k}{2}=m-\frac{k}{2}\end{cases} \]显然 \(x,y\) 为不是整数，不成立。
因此得证。
代码细节
注意 \(l,r\) 都是负数时加特判，把他变成正数的情况。
因为 c++ 在对负数取模时，会先把负数去掉，把他当成正数后取模，最后再加上负号。和我们先模在加再模的方式不同。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
ll t,l,r;
int main()
{
freopen("construct.in","r",stdin);
freopen("construct.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
cin>>l>>r;
ll rg=r-l+1;
if(r<0)
{
l*=-1;
r*=-1;
swap(l,r);
}
if(r%4==0)r-=2;
else if(r%4==1)r-=3;
else if(r%4==3)r-=1;
cout<<rg-ll(ceil((r-l+1)/4.0))<<endl;
}
return 0;
}