#include using namespace std; using int64 = long long; int main() { int P, Q; cin >> P >> Q; vector< pair< pair< int, int >, int > > rad; int ptr = 1; while(ptr <= P) { int ok = ptr, ng = P + 1; int real = P / ptr; while(ng - ok > 1) { int mid = (ok + ng) / 2; if(P / mid == real) ok = mid; else ng = mid; } rad.emplace_back(make_pair(ptr, ok), P / ptr); ptr = ok + 1; } vector< int64 > sum; sum.push_back(0); int64 add = 0LL; for(auto &p : rad) { auto range = p.first; auto val = p.second; int latte = range.first; int malta = range.second; add += val * (1LL * latte * (latte - 1) / 2); add -= val * (1LL * malta * (malta + 1) / 2); sum.push_back(add); } auto get = [&](int L) { __int128_t add = 1LL * P * L; auto it1 = lower_bound(begin(rad), end(rad), make_pair(make_pair(L, -1), L)) - begin(rad); --it1; add += sum[it1]; for(int i = it1; i < rad.size(); i++) { auto &p = rad[i]; auto range = p.first; auto val = p.second; int latte = range.first; int malta = min(range.second, L); if(latte > malta) break; add += val * (1LL * latte * (latte - 1) / 2); add -= val * (1LL * malta * (malta + 1) / 2); } return (int64) add; }; while(Q--) { int L, R; cin >> L >> R; cout << get(R) - get(L - 1) << endl; } }