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;
s:string;
procedure citeste(var a,b:int64);
          var c:byte;
          begin
          c:=1;
          a:=0;
          while s[c]<>' ' do
                begin
                a:=a*10+ord(s[c])-48;
                inc(c);
                end;
          inc(c);
          b:=0;
          while c<=length(s) do
                begin
                b:=b*10+ord(s[c])-48;
                inc(c);
                end;
          end;
begin
assign(f,'pinex.in');
assign(g,'pinex.out');
reset(f);rewrite(g);
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,s);
    citeste(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.