unsigned n;b[99],*p=b,u,v;main(m){for(;~scanf("%d%d",&u,&v);n=u,m=v)n?*p++=n,*p++=m:0;for(v=0;v||printf("%d\n",n),m--;)for(v=1,p=b;*p;p+=2)*p*n%p[1]<v?v=!(n=*p*n/p[1]):0;}