곱하기 게임
시간 제한2초메모리 제한128 MB
실수 X와 최대 0.9인 카드 최대 6개가 주어질 때, 최적 플레이 하에서 X를 1 이하로 먼저 만드는 승자를 구합니다.
문제
Nils와 Mikael은 하나의 실수 X와 K개의 카드를 사용해 게임을 한다. 1 < X < 10,000이고, 각 카드에는 0보다 크고 0.9 이하인 실수가 적혀 있다.
두 사람은 Nils부터 시작해 번갈아 턴을 가진다. 자신의 턴에는 반드시 카드 한 장을 고르고, 현재 X에 그 카드의 수를 곱해 새로운 X를 만든다. 카드는 사라지지 않으므로 같은 카드를 여러 번 선택할 수 있다.
이 과정을 반복하다가 처음으로 X를 1 이하로 만든 사람이 승리한다. 두 사람 모두 항상 자신에게 가장 유리한 선택을 한다고 할 때, 승자를 구하시오.
실수 연산에는 반올림 오차가 있을 수 있지만, 답이 미세한 입력 변화에 따라 달라지는 데이터는 주어지지 않는다.
입력
첫째 줄에 데이터의 개수 T가 주어진다. 1 ≤ T ≤ 55이다.
다음 T개의 줄에는 각 데이터가 주어진다. 각 줄은 실수 X, 정수 K, 그리고 카드에 적힌 K개의 실수로 이루어진다. 1 ≤ K ≤ 6이며, 입력되는 모든 실수는 유효 숫자가 6개를 넘지 않는다.
출력
각 데이터마다 승자의 이름인 Nils 또는 Mikael을 한 줄에 출력한다.