212

36

var        a,b,c,d:longint;function f(b:longint):longint;var        t,y:int64;begin        t:=1;        y:=2;        while b<>0 do        begin                if(b and 1)=1 then                        t:=(t*y)mod 12345678;                y:=(y*y)mod 12345678;                b:=b shr 1;        end;        exit(t);end;begin        assign(input,'color.in');reset(input);        assign(output,'color.out');rewrite(output);        readln(a);        for b:=1 to a do        begin                readln(c);                if c=1 then begin writeln(3);continue;end;                if c mod 2=1 then                        d:=-2                else                        d:=2;                writeln((f(c)+d)mod 12345678);        end;        close(input);        close(output);end.