小明和小红决定用一场博弈来决定谁才是真正的数字大师。
定义一个整数 关于基数 （）是“合法的”，当且仅当 在 进制表示下所有数位上的数字之积能够整除 。
游戏规则如下：
- 初始给定一个正整数 。
- 首先由小明选择一个基数 （），并告知小红。
- 之后两人轮流执行操作，小明先手。
- 每轮操作，当前玩家必须选取一个整数 ，满足：
- 选取后，将 更新为 。
- 若某轮操作者无法找到满足条件的 ，则该玩家输掉整场游戏。
假设两人都足够聪明并采取最优策略，小明想知道：能使自己获胜的最小的 是多少？ 如果不存在这样的 ，则输出 。
他们会进行多局游戏，你需要对每一局给出回答。
