#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a>p>>q; const Int MAX = 1e6; vector dp(MAX,0); for(Int i=1;i dp2; dp2[MAX-1]=dp[MAX-1]; auto calc= [&](Int x)->Int{ if(xsecond+1; res=dp2[k-1]+(x-k+1)*p; auto sub= [&](Int a,Int b){ assert(p/a==p/b); res-=(p/a)*(a+b)*(b-a+1)/2; }; while(k>1; if(p/k==p/m) l=m; else r=m; } sub(k,l); k=r; } return res; }; for(Int i=0;i>l>>r; cout<