C.S.G.
시간 제한3초메모리 제한1024 MB
두 플레이어가 번갈아 가며, 이미 가져간 모든 카드와 서로소인 카드를 한 장씩 가져갑니다. 가져갈 카드가 없는 쪽이 지며, 최적으로 둘 때의 승자를 구합니다.
문제
게임 마스터 amsminn이 유망주 bnb2011과 게임을 하려고 한다. 게임은 1 이상 이하의 정수가 하나씩 적힌 카드 장이 놓인 책상에서 진행되며, 규칙은 다음과 같다.
- 게임은 교대로 진행되며,
amsminn이 먼저 시작한다. - 각 사람은 자기 차례에 책상에 남은 카드 중 하나를 가져간다. 이때 가져간 카드는 지금까지 두 사람이 가져간 카드 전부와 서로소여야 한다. 가져간 카드는 책상에서 사라진다.
- 자기 차례에 책상에 카드가 남아 있지 않거나, 규칙에 어긋나지 않는 카드를 가져갈 수 없는 사람이 진다.
두 수의 최대공약수가 이면 두 수를 서로소라고 한다. 두 사람이 최선을 다한다고 할 때 누가 이기는지 구하라.
입력
첫째 줄에 테스트 케이스의 수 가 주어진다.
각 테스트 케이스는 두 줄로 주어진다. 첫째 줄에는 카드에 적힐 수 있는 수의 최댓값 과 카드의 개수 이 공백으로 구분되어 주어진다. ;
둘째 줄에는 각 카드에 적힌 정수가 공백으로 구분되어 주어진다. 카드에 적힌 수는 1 이상 이하의 정수이다.
모든 테스트 케이스의 의 합은 이하이며, 입력으로 주어지는 모든 수는 정수이다.
출력
각 테스트 케이스에 대해 amsminn이 이기면 amsminn을, bnb2011이 이기면 bnb2011을 각 줄에 출력한다.