DiviDuelo timer 1s memory 1024MB

The Intense Challenges Players Club (ICPC) is hosting a DiviDuelo tournament.

DiviDuelo is a new two-player, turn-based game. In DiviDuelo, a number N is selected and the list of its divisors is written. For example, if N = 10 is selected, the list of numbers 1, 2, 5, 10 is written. Players alternate turns picking one still unpicked divisor from the list each turn, until all divisors have been picked.

The winner is determined by the greatest common divisor (GCD) of the numbers picked by the starting player. If the GCD is not equal to 1, the starting player wins. Otherwise, if the GCD is equal to 1, the other player wins.

The ICPC needs your help to prepare some statistics about the games played in the tournament. Given the value of N, determine if the starting player can win the game assuming both players play optimally.