#NC201610. Game

Game

题目描述

Nancy喜欢博弈!

Johnson和Nancy得到了一个神奇的多重集合,仅包含一个正整数n,两个人轮流进行操作。

一次操作选择集合中的一个数字 mm,将其分解为 m=abm=ab,其中 a,b>1a,b>1,从集合中移除 mm 并加入 a,ba,b。当谁无法执行此步操作时,对方获胜。

他们想知道,在Johnson和Nancy绝顶聪明的情况下,如果Nancy先手进行操作,最后的败者是谁?

输入格式

第一行:一个整数n。 数据满足:2≤n≤1092\leq n\leq10^9。

输出格式

共一行:一个字符串,表示最后的败者(Johnson或者Nancy)。

样例 1

4
Johnson

来源

牛客原题