Задача Game2016. Два учні розважаються під час нудного уроку. Wi-Fi у школі вимкнули, тому доводиться розважатися як це робили колись, граючи у якусь «тиху» гру на папері. Перший учень на ім’я Петро знайшов у зошиті з англійської мови сторінку з диктантом, і викреслив з тексту дві однакові літери, а на заміну їм додав одну якусь літеру. Наприклад, набір літер {a, b, a} він міг би перетворити в один з наборів {a, b}, {b, b}, {b, c}, . . . , {b, z}. (так як учні не дуже добре писали диктанти з англійської, в тексті були лише малі літери латинського алфавіту). Тоді аналогічним чином робить свій хід другий учень на ім’я Арсеній, а далі знову Петро – і так по черзі. Правил гри ніхто не порушує. Програє той, хто не може зробити черговий хід – на сторінці залишилися лише різні літери. Але хлопці у вільний від вивчення шкільної інформатики час займалися програмуванням. Тому вже на другій сторінці з диктантом їм стало не цікаво – переможця (звичайно, за оптимальної стратегії обох гравців) вони визначали, не розпочинаючи гру. Спробуйте і ви створити програму, яка може це зробити. Нагадаємо, що для гри використовувалися лише малі літери латинського алфавіту, а Петрик завжди ходить першим.
Технічні умови. Програма Game2016 читає з пристрою стандартного введення у першому рядку кількість партій, K (1<=K<=10) які встигли за урок зіграти Петрик та Арсеній а далі K рядків, у кожному з яких без пропусків записано рядок, що складається з Z(k) (1<=Z(k)<=100000) малих літер латинського алфавіту. Програма виводить на пристрій стандартного виведення без пропусків в один рядок K символів, кожен із яких має значення G, якщо виграє Петрик, або D, якщо виграє Арсеній.
Приклад
Введення Виведення
2 DG
abc
aba