약수 지우기 게임 1

A와 B가 약수 지우기 게임을 한다. 칠판에는 1부터 $N$까지의 자연수가 하나씩 적혀 있다.

자기 차례가 된 사람은 칠판에 남아 있는 수 하나를 골라 지우고, 그 수의 약수 중 칠판에 남아 있는 수도 모두 지운다. 예를 들어 칠판에 2, 3, 4, 5, 6이 남아 있을 때 6을 고르면 6과 함께 약수인 2와 3도 지운다. 자기 차례에 아무것도 지우지 않고 넘길 수는 없다. 마지막 수를 지운 사람이 진다.

A가 먼저 시작하고 두 사람 모두 최적으로 둘 때, 이기는 사람을 구하라.

첫째 줄에 $N$이 주어진다. $N$은 1,000,000보다 작거나 같은 자연수이다.

첫째 줄에 A가 이기면 A를, B가 이기면 B를 출력한다.

$N = 4$이면 A는 첫 차례에 4를 골라 4와 그 약수인 2, 1을 지운다. 칠판에는 3만 남고, B는 3을 지울 수밖에 없어 진다.