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