GCD Guessing Game

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4267 [PDF](https://uva.onlinejudge.org/external/15/p1521.pdf)

**本题在单测试点内有多组测试数据，请读入到 EOF。** 给定 $n (2 \leq n \leq 10^4)$，玩一个猜数游戏。目标为 $p (p \in [1, n])$。 每一次可以猜一个数 $x$，会告诉你 $\gcd(x, p)$。 求在 **最坏** 情况下，至少需要猜几次 **保证** 猜出 $p$。

对于每一组数据，输出答案并换行。

6

2

Translated by @[longgod](/user/39675), retranslated by @[Carroty_cat](/user/912750).