var v:array[0..1000005] of longint;
p,st:array[0..40] of longint;
m,i,j,last,max,nr,c:longint;
a,b,sol,prod:int64;
f,g:text;
bufin,bufout:array[1..65000] of byte;
procedure bktr(poz:longint);
          var i:longint;
          begin
          for i:=st[poz-1]+1 to nr do
              begin
              st[poz]:=i;
              if poz<j then
                 bktr(poz+1)
              else
                  begin
                  prod:=1;
                  for c:=1 to j do
                      prod:=prod*p[st[c]];
                  if j mod 2=0 then
                     sol:=sol-a div prod
                  else
                      sol:=sol+a div prod;
                  end;
              end;
          end;
begin
assign(f,'pinex.in');
assign(g,'pinex.out');
reset(f);rewrite(g);
settextbuf(f,bufin);
settextbuf(g,bufout);
for i:=2 to 1000000 do
    if v[i]=0 then
       begin
       for j:=i to 1000000 div i do
           v[j*i]:=1;
       v[last]:=i;
       last:=i;
       end;
readln(f,m);
for i:=1 to m do
    begin
    readln(f,a,b);
    nr:=0;
    j:=2;
    max:=trunc(sqrt(b));
    while j<=max do
          begin
          if b mod j=0 then
             begin
             inc(nr);
             p[nr]:=j;
             while b mod j=0 do
                   b:=b div j;
             end;
          j:=v[j];
          end;
    if b>1 then
       begin
       inc(nr);
       p[nr]:=b;
       end;
    sol:=0;
    for j:=1 to nr do
        sol:=sol+a div p[j];
    for j:=2 to nr do
        bktr(1);
    writeln(g,a-sol);
    end;
close(f);close(g);
end.