def my_gcd(a, b):
    ret = 0
    if a < b:
        a, b = b, a
    if b == 0:
        ret = a
    else:
        ret = my_gcd(b, a % b)
    return ret

divisor = [-1 for _ in range(300002)]
for i in range(2, 300001):
    for j in range(2, 300000 // i + 1):
        divisor[j * i] = j

phi = [0 for _ in range(300002)]
for i in range(2, 300001):
    now = i
    div = -1
    tot = i
    while True:
        if divisor[now] == -1:
            if now != div:
                tot = tot * (now - 1)
                tot //= now
            break
        if div != divisor[now]:
            div = divisor[now]
            tot = tot * (div - 1)
            tot //= div
        now //= div
    phi[i] = tot

phi_sum = [0 for _ in range(300002)]
for i in range(2, 300001):
    phi_sum[i] = phi_sum[i - 1] + phi[i]

T = int(input())
for _ in range(T):
    L, R = map(int, input().split())
    ans = 0
    for i in range(2, 401):
        k1 = (L - 1) // i
        k2 = R // i
        if k1 < k2:
            ans += phi[i]
    left = 0
    right = 1
    prev = R
    while True:
        if R < 400:
            break
        nl = (L - 1) // (left + 1)
        nr = R // (right + 1)
        
        val = max(nl, nr)
        if left != right:
            ans += (phi_sum[prev] - phi_sum[max(val, 400)])
        if val <= 400:
            break
        prev = val
        if nl >= nr:
            left += 1
        else:
            right += 1
    print(ans)