#include <bits/stdc++.h>
using namespace std;
ifstream f("cufar.in");
ofstream g("cufar.out");
//#define int long long
const int Max = 1e6 + 100;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int task;
int n;
vector < int > divi[Max];
bool prime[Max];
void init()
{
    int   i;
    const int last = 1e6;
    for(long long d=2;d*d<=last;d++)
    {
        if(prime[d] == 0)
        {
            for(i=d*d;i<=last;i+=d)
                prime[i] = 1;
        }
    }
    for(i=2;i<=last;i+=2)
        divi[i].push_back(2);
    for(i=3;i<=last;i+=2)
    {
        if(prime[i] == 0)
        {
            int  j;
            for(j=i;j<=last;j+=i)
                divi[j].push_back(i);
        }
    }
}


void read()
{
    f>>task>>n;
}
void solve()
{
    init();
    long long  suma = 0;
    int i;
    int x,div;
    for(i=1;i<=n;i++)
    {

        f>>x>>div;
        suma += divi[x][div-1];
    }
    g<<suma;
}

int32_t main()
{

    read();
    solve();


    return 0;
}