23764번 - 서로소 게임

문제

준혁이와 영우가 서로소 게임을 하려고 한다.

서로소 게임은 칠판에 $N$개의 수가 써져 있는 상태로 시작한다. 두 사람은 서로 턴을 번갈아가면서 게임을 진행한다.

각 사람의 턴이 되면 칠판에 있는 수 하나를 골라서, 고른 수는 지우고 두 개의 자연수를 새로 적어야 한다. 이 두 수는 서로소가 아니어야 하며, 합하여 지운 수가 되어야 한다. 예를 들어 8을 지운 뒤 2와 6를 쓸 수 있다. 그러나 3과 5는 합하여 8이지만 서로소이기 때문에 적을 수 없다.

더 이상 턴을 진행할 수 없는 사람이 게임에서 지게 된다.

그런데 준혁이는 여러 개의 수 중 어떤 것을 골라야 유리할 지 고민에 빠지기 시작했다. 준혁이를 기다릴 수 없었던 영우는, 수를 고를 때 고를 수 있는 수 중 가장 작은 수를 고르자는 규칙을 추가하였다. 예를 들어 칠판에 4, 8, 9가 적혀있다면, 4를 골라 턴을 진행하는 것이 가능하기 때문에 8이나 9를 골라서는 안된다.

게임은 준혁이가 먼저 시작한다. 두 사람 모두 최적의 방법으로 게임을 진행할 때, 누가 이길지 구해보자.

입력

첫째 줄에 처음에 써져 있는 수의 개수 $N$이 주어진다. (1ドル\leq N \leq 10^4$)

둘째 줄에 $N$개의 수 $a_1, a_2,\ldots ,a_n$이 공백을 사이에 두고 주어진다. (1ドル\leq a_i \leq 10^9$)

출력

첫째 줄에 준혁이가 이기면 "6", 영우가 이기면 "52"를 출력한다. (따옴표 제외)

제한

힌트

첫 번째 예제에서, 준혁이가 4를 지우고 2, 2를 적으면 이긴다.