Метро#1725
Деякі міста мають мережу метро, структуровану як дерево, тобто між будь-якими двома станціями існує рівно один шлях. У таких мережах є унікальна центральна станція. Уявіть, що ви турист у такому місті, який бажає дослідити всю мережу метро. Ви починаєте з центральної станції, випадково обираєте напрямок і вирушаєте до наступної станції. Кожного разу, коли ви прибуваєте на станцію, ви обираєте одну з гілок, якою ще не подорожували. Якщо на станції не залишилось невивчених гілок, ви повертаєтесь на станцію, з якої вперше потрапили на цю станцію. Цей процес триває, допоки ви не пройдете всі гілки двічі (по одному разу в кожному напрямку). На цьому етапі ви знову опинитесь на центральній станції. Таку подорож можна представити у вигляді бінарного рядка: цифра 0 означає переміщення від центральної станції, а цифра 1 — переміщення до центральної станції. Оскільки невивчені гілки вибираються випадково, для однієї й тієї ж мережі метро може існувати декілька рядків-кодів.
Напишіть програму, яка визначає, чи описують два бінарні рядки одну й ту саму мережу метро.
У першому рядку вхідних даних міститься одне ціле число (1 \leq N \leq 20) — кількість тестових випадків. Далі наведено пар рядків, кожен з яких складається з цифр та , довжина кожного рядка не перевищує символів.
Кожен рядок кодує один з можливих маршрутів дослідження мережі метро.
Для кожної пари рядків виведіть "same", якщо обидва рядки кодують дослідження однієї й тієї ж мережі метро, або "different", якщо досліджені мережі метро різні.
Приклад 1