var n,i:longint;
    flag:boolean;
function fp(n:longint):longint;
var f,ff:boolean;
    a,b:longint;
begin
  f:=true;
  a:=n;
  b:=n;
  while f do
  begin
    ff:=true;
    dec(a);
    for i:=2 to trunc(sqrt(a)) do
    if a mod i=0 then begin ff:=false;break; end;
    if ff then break;
  end;
  while f do
  begin
    ff:=true;
    inc(b);
    for i:=2 to trunc(sqrt(b)) do
    if b mod i=0 then begin ff:=false;break; end;
    if ff then break;
  end;
  fp:=b-a;
end;
begin
  readln(n);
  while n<>0 do
  begin
    flag:=true;
    for i:=2 to trunc(sqrt(n)) do
    if n mod i=0 then begin flag:=false; writeln(fp(n)); break; end;
    if flag then writeln('0');
    readln(n);
  end;
end.