program chocolate;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var i,j,k,l,m,n:longint;
function step(x,y:longint):longint;
begin
   if y=0 then step:=1 else step:=step(x,y-1)*x;
end;
begin
  reset(input,'chocolate.in');
  read(n);
  for i:=1 to n do
  begin
     read(k);
     if k=2 then
     begin
        writeln(3);
     end else
     if odd(k) then
     begin
        writeln(0);
     end else
     begin
        j:=step(3,k div 2);
        l:=step(2,(k div 2) - 1);
        writeln(j+l);
     end;
  end;
end.
