#LUOGUP1048. 数字游戏

数字游戏

题目描述

KC 邀请他的两个小弟 K 和 C 玩起了数字游戏。游戏是 K 和 C 轮流操作进行的,K 为先手。KC 会先给定一个数字 QQ,每次操作玩家必须写出当前数字的一个因数来代替当前数字,但是这个因数不能是 11 和它本身。例如当前数字为 66,那么可以用 2,32, 3 来代替,但是 1166 就不行。现在规定第一个没有数字可以写出的玩家为胜者。K 在已知 QQ 的情况,想知道自己作为先手能不能胜利,若能胜利,那么第一次写出的可以制胜的最小数字是多少呢?整个游戏过程我们认为 K 和C用的都是最优策略。

输入格式

仅一行,一个正整数 QQ

输出格式

第一行是 112211 表示 K 能胜利,22 表示 C 能胜利。

若 K 能胜利,则在第二行输出第一次写出的可以制胜的最小数字。

若是第一次就无法写出数字,则认为第一次写出的可以制胜的最小数字为 00

6

2

30

1
6

提示

对于 30%30 \% 的数据,Q50Q \le 50
对于 100%100 \% 的数据,2Q10132 \le Q \le {10}^{13}