$_=<>;<>=~/.$/;eval"0while\$%++<1e3&&s/$`$&/$&/";print$%%1001-1