const   SMALL_PRIME = 665000;
        MAX_SMALL_PRIME = 10000001;
        THE_N = 109;
        MAX_K_POWER = 10; { Will check all k < 10^MAX_K_POWER }

type SmallArray = array[1..SMALL_PRIME] of dword;

Var
    pr, nn: SmallArray;
    c: dword;

function PowMod(n, p : dword) : dword;
  const ONE: dword = 1;
  var tmp: dword;
begin
    If (n <= 31) Then
        PowMod := (ONE shl n) mod p
    Else 
    Begin
        tmp := PowMod(n div 2, p);
        asm
            movl    tmp, %eax
            mull    %eax
            divl    p
            movl    %edx, tmp
        end;
        If Odd(n) Then
            PowMod := (tmp + tmp) Mod p
        Else
            PowMod := tmp;
    end
end;

procedure TestK(k : qword);
var i, p, x, k1, n, n2 : dword;
begin

    For i := 4 To c do
    begin
        p := pr[i]; n := nn[i]; n2 := n + n; if n2 > p then n2 := n2 - p;
        {k1 := k Mod p;}
        asm
            movl    k+4, %eax
            xorl    %edx, %edx
            divl    p
            movl    k, %eax
            divl    p
            movl    %edx, k1
        end;
        
        { x := k1 * nn[i] Mod p; }
        asm
            movl    n, %eax
            mull    k1
            divl    p
            movl    %edx, x
        end;
        If (x = 1) Or (x = p-1) Then exit;
        x := x + x;
        If (x = p+1) Or (x = p-1) Then Exit;
        If (n = k1) Or (n2 = k1) Or (n + k1 = p) Or (n2 + k1 = p)  Then Exit;
    end;
    writeln(k);
end;

Var i, j, p: Dword;
    pflag : Boolean;
    k,maxk: qword;
begin

pr[1] := 2;
pr[2] := 3;
pr[3] := 5;
pr[4] := 7;
pr[5] := 11;
pr[6] := 13;
pr[7] := 17;
pr[8] := 19;
c := 8;

For i := 21 To MAX_SMALL_PRIME do
begin
    if (i And 1) = 0 then continue;
    pflag := True;
    For j := 2 To c do
    begin
        p := pr[j];
        If (i Mod p) = 0 Then
        begin
            pflag := False;
            break;
        End;
        If Word(p)*Word(p) > i Then break;
    End;
    If pflag Then
    begin
        c := c + 1;
        pr[c] := i;
    End;
end;
Writeln('c = ', c);

For i := 4 To c do
begin
    nn[i] := PowMod(THE_N, pr[i]);
end;

maxk := 1;
for i:=1 to MAX_K_POWER do
  maxk := maxk * 10;

k := 15; 
repeat
    TestK(k);
    k := k + 30;
until k > maxk;
end.