#include?
#define?N?10009
main（）
{int?n=Ns[N]a[N]b[N];int?t;
while?（--n）s[n]=0;
s[1]=5;s[0]=2;
n=N;
a[0]=0;
while（--n）a[n]=0;a[1]=5;b[0]=0;
for（t=3;t<=（N+43）/3;++t）
{
?for（n=1;n?{
?b[n]=（10*b[n-1]+a[n]）%t;
?a[n]=（10*b[n-1]+a