Задача 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