program Project222131;

{$APPTYPE CONSOLE}

uses
  SysUtils;
var
  n, i, j, i1, f, c: integer;
  a: array[1..1900000000] of boolean;

begin
  readln(n);
  while (n <= 2) do
  begin
    writeln(1);
    readln;
    readln;
    exit;
  end;
  while (n <= 14) do
  begin
    writeln(3);
    readln;
    readln;
    exit;
  end;
  while (n <= 86) do
  begin
    writeln(15);
    readln;
    readln;
    exit;
  end;
  while (n <= 518) do
  begin
    writeln(87);
    readln;
    readln;
    exit;
  end;
  while (n <= 3110) do
  begin
    writeln(519);
    readln;
    readln;
    exit;
  end;
  while (n <= 18662) do
  begin
    writeln(3111);
    readln;
    readln;
    exit;
  end;
  while (n <= 111974) do
  begin
    writeln(18663);
    readln;
    readln;
    exit;
  end;
  while (n <= 671846) do
  begin
    writeln(111975);
    readln;
    readln;
    exit;
  end;
  while (n <= 4031078) do
  begin
    writeln(671847);
    readln;
    readln;
    exit;
  end;
  while (n <= 24186470) do
  begin
    writeln(4031079);
    readln;
    readln;
    exit;
  end;
  writeln(24186471);
  readln;
  readln;
end.