Игра с шоколадкой
(Время: 3 сек. Память: 16 Мб Сложность: 69%)
Петя с Андреем играют в интересную игру. Для этой игры им необходимо k шоколадок, каждая из которых имеет форму прямоугольника, i-ая из них имеет размер wi на hi долек.
Петя с Андреем ходят по очереди, за один ход игрок должен взять со стола одну шоколадку, разломать ее на две неравных непустых части, и их обе положить обратно на стол. При этом обе получающиеся части должны иметь форму прямоугольника, длины сторон которого выражаются целым числом долек.
Первый ход в этой игре делает Петя. Проигрывает игрок, который не может сделать ход. Победитель после этого получает весь шоколад, лежащий на столе.
Ваша задача определить, кто из игроков выиграет при оптимальной игре обоих.
Входные данные
Входной файл INPUT.TXT содержит содержит несколько наборов входных данных. Первая строка входного файла содержит количество T наборов входных данных (1 ≤ T ≤ 1000).
Каждый набор входных данных описывается следующим образом. Первая строка описания содержит число k (1 ≤ k ≤ 100) – количество шоколадок, лежащих на столе в начале игры. Последующие k строк описывают шоколадки: i-ая из этих строк содержит два числа: wi и hi – размеры соответствующей шоколадки (1 ≤ wi, hi ≤ 100).
Выходные данные
Для каждого набора входных данных в выходной файл OUTPUT.TXT выведите ответ согласно формату, приведенному в примерах.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1
1 1
1
3 1
2
1 1
3 1 | Game 1: Andrew wins.
Game 2: Petr wins.
Game 3: Petr wins. |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
