1131. Divisor Game

Alice and Bob play with a number n, Alice moving first. On each turn a player picks a divisor x of the current n with 0 < x < n, then replaces n with n - x. A player who cannot move loses. Assuming optimal play, return true if Alice wins. The input is JSON {n}.

Input: JSON {n}.

Output: Boolean — true if Alice wins.

Examples

Input: {"n":2}
Output: true
Explanation: Alice picks 1, leaving Bob with 1.

Input: {"n":3}
Output: false
Explanation: Alice is forced into a losing move.

Input: {"n":4}
Output: true
Explanation: Alice wins with optimal play.

Constraints

• 1<=n<=1000

Asked by