Задача Tri2015. Мешканці далекої планети Трианглії вирішили побудувати новий вівтар у Храмі Священної Трійки. Вівтар повинен мати форму рівностороннього трикутника з довжиною сторони n см, і складеним з камінців у формі рівносторонніх трикутників з стороною 1 см. При цьому n має бути степенем числа три: n = 3k (рис. 1).
Рис. 1. Приклад вівтаря з довжиною сторони n=3см
Кожен з маленьких трикутників-камінців має бути пофарбованим в один з трьох кольорів: червоний, зелений чи синій. Для того, аби визначити колір кожного каменю майбутнього вівтаря, спочатку створюють допоміжний шар (фундамент) з n+1 каменів, по одному на кожного мешканця. Далі вівтар будується пошарово - спочатку шар над фундаментом, потім другий шар, і так до самої вершини, дотримуючись двох правил:
• якщо кольори двох сусідніх трикутників внизу якогось трикутника різні, то цей трикутник має бути третього кольору;
• якщо колір двох сусідніх трикутників внизу співпадає, то цей же колір повинен мати і поточний трикутник.
Герой Трианглії Тривася Трипупкін спізнився на момент закладки фундаменту. Решта n його друзів вже поклали свої камінці у фундамент, так що там залишилось місце лише для крайнього правого трикутника (синій камінець в фундаменті на рис. 1). Тривася хоче дізнатися, камінець якого кольору він має покласти у фундамент, аби вершина вівтаря була пофарбована в зелений колір.
Технічні умови. Програма Tri2015 читає з пристрою стандартного введення ціле число 1 <= M <= 10 – кількість фундаментів. Далі програма читає з того ж рядка через пропуски М послідовностей символів з множини {r,g,b}, що відображають кольори камінців у майже готовому фундаменті зліва направо (у кожній послідовності символи записані без пропусків, кількість символів у кожній послідовності n = 3k, де k ⩽ 10 , тобто n ⩽ 59049). Програма виводить на пристрій стандартного виведення М підмножин множини {r,g,b}. Кожна підмножина записана в вигляді одного або послідовності символів без пропусків. Послідовності розділено одним пропуском. Якщо Тривася не може отримати зелену вершину жодним з способів, вивести єдиний символ n.
Приклад
Введення 2 rgg ggrggrggr
Виведення: b g