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