#include <bits/stdc++.h> // #include <atcoder/all> // using namespace atcoder; using namespace std; // #define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; typedef pair<int, int> P; #define rep(i, s, n) for (int i = (s); i <= (n); ++i) #define per(i, n, s) for (int i = (n); i >= (s); --i) #define rep_(i, s, n) for (int i = (s); i < (n); ++i) #define per_(i, n, s) for (int i = (n); i > (s); --i) #define FOR(i, s, e, step) for (int i = s; i <= e; i += step) #define FOR_(i, s, e, step) for (int i = s; i < e; i += step) #define fora(i, v) for (auto i : (v)) #define fori(i, v) for (auto i = (v).begin(); i != (v).end(); ++i) #define all(v) (v).begin(), (v).end() #define all_(v, n) (v) + 1, (v) + (n) + 1 typedef pair<ll, ll> LP; typedef double ld; typedef pair<ld, ld> LDP; const ld eps = 1e-10; const ld pi = acosl(-1.0); const ll mod = 998244353; template <typename T> void chmin(T& a, T b) { a = min(a, b); } template <typename T> void chmax(T& a, T b) { a = max(a, b); } ll qpow(ll x, ll n, ll m = mod) { if (n < 0) { ll res = qpow(x, -n, m); return qpow(res, m - 2, m); } if (abs(x) >= m) x %= m; if (x < 0) x += m; ll res = 1; while (n) { if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; } // mod should be <2^31 struct modint { int n; modint() : n(0) { ; } modint(ll m) { if (m < 0 || mod <= m) { m %= mod; if (m < 0) m += mod; } n = m; } operator int() { return n; } }; bool operator==(modint a, modint b) { return a.n == b.n; } bool operator<(modint a, modint b) { return a.n < b.n; } modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod) a.n -= (int)mod; return a; } modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0) a.n += (int)mod; return a; } modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; } modint operator+(modint a, modint b) { return a += b; } modint operator-(modint a, modint b) { return a -= b; } modint operator*(modint a, modint b) { return a *= b; } modint operator^(modint a, ll n) { if (n == 0) return modint(1); modint res = (a * a) ^ (n / 2); if (n % 2) res = res * a; return res; } ll inv(ll a, ll p) { return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p); } modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); } modint operator/=(modint& a, modint b) { a = a / b; return a; } const int max_n = 1 << 20; modint fact[max_n], factinv[max_n]; void init_f() { fact[0] = modint(1); for (int i = 0; i < max_n - 1; i++) { fact[i + 1] = fact[i] * modint(i + 1); } factinv[max_n - 1] = modint(1) / fact[max_n - 1]; for (int i = max_n - 2; i >= 0; i--) { factinv[i] = factinv[i + 1] * modint(i + 1); } } modint comb(int a, int b) { if (a < 0 || b < 0 || a < b) return 0; return fact[a] * factinv[b] * factinv[a - b]; } modint combP(int a, int b) { if (a < 0 || b < 0 || a < b) return 0; return fact[a] * factinv[a - b]; } ll gcd(ll a, ll b) { a = abs(a); b = abs(b); if (a < b) swap(a, b); while (b) { ll r = a % b; a = b; b = r; } return a; } // int dx[4] = { 1,0,-1,0 }; // int dy[4] = { 0,1,0,-1 }; const int N = 200000; struct que { int l, r; int id; } q[200005]; struct point { int l, r, v; } pot[5000005]; int cnt; vector<int> yin[200005]; ll tree[200005]; inline int lowbit(int x) { return x & -x; } void add(int x, int v) { while (x <= N) { tree[x] += v; x += lowbit(x); } } ll sum(int x) { ll res = 0; while (x > 0) { res += tree[x]; x -= lowbit(x); } return res; } ll qans[200005]; // signed main() { int main() { // freopen(".in", "r",stdin); // freopen(".out","w",stdout); ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; rep(i, 1, t) { cin >> q[i].l >> q[i].r; q[i].id = i; } sort(all_(q, t), [](const que& x, const que& y) { return x.r == y.r ? x.l < y.l : x.r < y.r; }); rep(i, 1, N) FOR(j, i * 2, N, i) yin[j].push_back(i); rep(i, 1, N) { int s = yin[i].size(); rep_(j, 0, s) { pot[++cnt] = {yin[i][j], i, s - j - 1}; } } int w = 1; //[1,w) rep(i, 1, t) { int ql = q[i].l, qr = q[i].r; while (w <= cnt && pot[w].r <= qr) { add(pot[w].l, pot[w].v); w++; } ll ans = 1ll * (qr - ql + 1) * (qr - ql) * (qr - ql - 1) / 6; ans -= max(0, qr / 6 - (ql - 1) / 3); ans -= max(0, qr / 15 - (ql - 1) / 6); ans -= sum(qr) - sum(ql - 1); qans[q[i].id] = ans; } rep(i, 1, t) { cout << qans[i] << '\n'; } return 0; } /*tips: read pls use 'cin'; write pls use 'printf' or 'cout', use '\n' instead of 'endl'; debug pls use 'cerr'. remember to initialize variables, note that the array is out of bounds. */ // 2k->3,4,6 or 6,10,15, O(1) // k->二维数点