整数$x$を質問して答え$N-x$が帰ってくること（つまり、末尾まで一致していること）と、問題の列が長さ$x$のprefixの繰り返しになっていることは同値である。質問する$x$は$N$の約数だけでよくて、 $10^6$以下の自然数の約数の数は高々$240$個なので、すべて調べれば部分点が取れる。
$N$を素因数分解して$N = p_1^{e_1}p_2^{e_2}...p_k^{e_k}$とする。$N/p_i^{e_i}$を質問して末尾まで一致している$\Leftrightarrow$素因数$p_i$は必要ない、が成り立つので、これで必要な素因数を割り出したあと、それぞれの指数に関して二分探索すればよい。高々9回で可能というのは全列挙で示すしかなさそう？
