Лорд Бредли на северном полюсе
Начинался полярный рассвет. Лорд Брэдли стоит точно на Северном полюсе, лицом в сторону своего далекого дома в Гринвиче. Со всех сторон Земли на него движутся сердитые белые медведи чтобы отомстить. У лорда Брэдли есть только его верная винтовка. Он никогда не промахивается, и может сделать выстрел (или любое количество выстрелов) в любой период времени. Винтовка имеет необычную линию огня - она может поразить цель на любом расстоянии, вплоть до Южного полюса.
Единственная проблема заключается в изменении направления выстрела: для сохранения своей совершенной концентрации лорд Бредли всегда поворачивается со скоростью одной арксекунды (1" = 1/3600 * 1° за одну секунду). Удастся ли ему пострелять всех медведей, или он сам станет их завтраком?
Предположим, что Земля является совершенной сферой, длина экватора составляет в точности 40 320 км, а все медведи двигаются прямо на Бредли с константной скоростью 28 км/ч. Медведь может быть убит даже в упор (в момент достижения им Северного Полюса), однако направление ружья должно совпадать с направлением откуда пришел медведь. Зная начальные географические координаты всех медведей, определите, сможет ли выжить лорд Бредли.
Входные данные
Первая строка содержит количество тестов t.
Первая строка каждого теста содержит количество медведей n (1 ≤ n ≤ 1 000). В следующих n строках заданы координаты медведей (широта и долгота, используя * для градусов, ' для минут и " для секунд как показано в примере). Ни градусы, ни минуты, ни секунды не могут быть пропущены. Все числа являются неотрицательными целыми. Как и обычно, через N обозначается северное полушарие, через S южное, E - восток от Гринвича, W - запад.
Выходные данные
Для каждого теста вывести в отдельной строке одно слово: ALIVE если Бредли сможет победить медведей или EATEN иначе.