var fi,fo:text;
    n,ct,m,l,phi,nenner,zahler:int64;
    {prime:array[1..50000]of longint;
    puteri:array[1..100000]of longint;}
   { prime2:array[1..100000]of byte;
    primee:array[1..90000]of longint;}
    ap:array[1..100000]of int64;
{procedure gen(ba:longint);
var i,j:int64;
begin
  i:=3;
  primee[1]:=2;
  l:=1;
  prime2[1]:=1;
  while i<=ba do
    begin
      if prime2[i]=0 then
        begin
          j:=i*i;
          inc(l);
          primee[l]:=i;
          while j<=ba do
             begin
                prime2[j]:=1; inc(j,i);
             end;
        end;
      inc(i,2);
    end;
end;  }
procedure desc(n:longint);
var i:longint;
    r:int64;
begin
  nenner:=1; zahler:=1;
  if n and 1=0 then
    begin
      while n and 1=0 do
        n:=n shr 1;
      nenner:=nenner*2;
      if n=1 then exit;
    end;
  i:=3;
  while i<=trunc(sqrt(n)) do
    begin
      if n mod i=0 then
        begin
          while n mod i=0 do
            n:=n div i;
          nenner:=nenner*i;
          zahler:=(i-1)*zahler;
          if n=1 then exit;
        end;
       inc(i,2);
   end;
   nenner:=nenner*n;
   zahler:=zahler*(n-1);
end;
procedure solv(n:longint);
var rez:int64;
    i:longint;
begin
  desc(n);
  phi:=n*zahler div nenner;
  rez:=n*phi shl 1;
  writeln(fo,rez);
  ap[n]:=rez;
end;
var i:longint;
begin
  assign(fi,'sum.in'); reset(fi);
  assign(fo,'sum.out'); rewrite(fo);
  read(fi,m);
 { gen(100000);}
  for i:=1 to m do
    begin
      read(fi,n);
      if ap[n]<>0 then writeln(fo,ap[n])
        else
          solv(n);
    end;
  close(fi);
  close(fo);
end.