1249. Stone Game IV

A pile holds n stones. Alice and Bob alternate turns, starting with Alice, and each turn a player removes a non-zero square number of stones. 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":1}
Output: true
Explanation: Alice takes the single stone.

Input: {"n":2}
Output: false
Explanation: Alice must take 1, leaving Bob a win.

Input: {"n":4}
Output: true
Explanation: Alice takes all four.

Constraints

• 1<=n<=10^5

Asked by