完美三元组(normal version)

Description

注意此题与easy唯一的区别是数据范围。 输出区间 [l,r] 包含的完美三元组的个数。一个三元组是完美三元组，当且仅当指元组中前两个数都能整除第三个数。 即输出区间[l,r] 内满足 l<=a<=b<=c<=r 且a|c且b|c的三元组 (a,b,c) 的个数.(x|y表示y能被x整除)

Input

第一行输入一个正整数T(1<=T<=20)，表示有T组数据. 接下来T行，每行包含两个正整数l,r(1<= l<= r<= 100000).

Output

对于每一组数据，输出一行一个整数表示区间内完美三元组的个数.

Sample Input

2 1 2 1 3

Sample Output

4 7

Hint

区间[1,2]内所有完美三元组为(1,1,1),(1,1,2),(1,2,2),(2,2,2)。 区间[1,3]内所有完美三元组为(1,1,1),(1,1,2),(1,1,3),(1,2,2),(1,3,3),(2,2,2),(3,3,3)。

#include <iostream>
 
using namespace std;
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        long long l,r,isprime[1000010],ans=0;
        scanf("%lld%lld",&l,&r);
        for(int i=0;i<=r;i++) isprime[i]=1;
        isprime[1]=1;
        for(int i=1;i<=r;i++){
            if(isprime[i]>0&&i>=l){
                for(int j=i*2;j<=r;j+=i){
                    if(j>r)
                        break;
                    isprime[j]++;
                }
            }
        }
        for(int i=l;i<=r;i++){
         ans+=(isprime[i]*(isprime[i]-1))/2+isprime[i];
        }
        printf("%lld\n",ans);
    }
}