char*p,a[999];m,l,x;main(n){for(p=a+998;~scanf("%d",&n);puts(p--))for(*--p=49;l=n;n--,p++){for(;*p|m;)m=!*p?x=l%m,l=m,x:(m*10+*p++%16)%n;for(;*--p|m;m/=10)m+=*p%16*n/l,*p=m%10+48;}}