f(x,n,t=1) = while (t-->=0, x=(x^2)%n); x

find cycle(x, n) = {
	my (y=f(x,n));
	while ((x=f(x,n))!=(y=f(f(y,n),n)),
	);
	my (c=[x]);
	while (x!=y=f(y,n),
		c=concat(c,y);
	);
	return (c);
}

count(x, y, sqx, sqy, p="*") = {
	if (#sqx[1+x]==0,
		return (1),
		prod(i=1, #sqx[1+x],
			sum(j=1, #sqy[1+y],
				count(sqx[1+x][i], sqy[1+y][j], sqx, sqy, Str(p"*"));
			);
		);
	);
}

a(n) = {
	my (nb=1);
	my (s=0);
	my (sqy=vector(n, k, []));
	for (x=0, n-1,
		my (y=f(x,n));
		sqy[1+y] = concat(sqy[1+y], x);
	);
	my (sqx=sqy);

	for (x=0, n-1,
		my (c=find cycle(x,n), cc=Set(c));
		if (!bittest(s, c[1]),
			for (i=1, #c,
				s = bitor(s, 2^c[i]);
				sqx[1+c[i]] = setminus(sqx[1+c[i]], cc);
			);

			my (t=0);
			for (v=0, n-1,
				if (v==f(v,n,#c),
					my (w=v, d=1);
					for (i=1, #c,
						d *= count(c[i], w, sqx, sqy);
						w = f(w,n);
					);
					t += d;
				);
			);
			nb *= t;
		);
	);
	return (nb);
}

for (n=1, oo, v=a(n); if (v>10^1000, break, print (n " " v)))

quit