var v:array[0..1000005] of longint;
p:array[0..40] of longint;
m,i,j,last,max,nr,c,count:longint;
a,b,sol,prod:int64;
f,g:text;
bufin,bufout:array[1..65000] of byte;
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:=1 to 1 shl nr do
        begin
        prod:=1;
        count:=0;
        for c:=1 to nr do
            if ((1 shl (c-1)) and j)<>0 then
               begin
               inc(count);
               prod:=prod*p[c];
               end;
        if count>1 then
           if count mod 2=0 then
              sol:=sol-(a div prod)
           else
               sol:=sol+(a div prod);
        end;
    writeln(g,a-sol);
    end;
close(f);close(g);
end.