Рабочее место участника

Некоторые города имеют сеть метро в форме дерева, т.е. для любой пары станций есть один и только способ добраться с одной станции на другую. Такие сети метро имеют уникальную центральную станцию. Представьте, что вы турист в таком городе и хотите изучить всю сеть метро. Вы стартуете на центральной станции, выбираете случайно одно из направлений и едете в вагоне на следующую станцию. Всякий раз, прибывая на станцию, вы выбираете одну из веток, по которой еще не ездили. Если таких веток на текущей станции не осталось, вы отправляетесь назад на ту станцию, откуда приехали на эту станцию в первый раз. Так продолжается до тех пор, пока вы не проедете по всем веткам дважды (по разу в каждом направлении). В этот момент вы должны быть на центральной станции. Такое путешествие можно закодировать как двоичную строку следующим образом. Цифрой 0 кодируется поездка, которая отдаляет нас от центральной станции, а цифрой 1 – поездка, которая приближает к центральной станции. Существует несколько возможных кодирующих строк для одной и той же сети метро, так как "неисследованные" ветки выбираются случайным образом.

Напишите программу, которая определяет, описывают ли две двоичные строки одну и ту же сеть метро или нет.

В первой строке входного файла содержится целое число `N` (`1\ ≤\ N\ ≤\ 20`) – количество тестов. Далее следует `N` пар строк, состоящих из цифр 0 и 1, длиной не более 3000 символов. В каждой строке закодировано одно корректное обследование сети метро.

В выходной файл для каждой пары строк вывести сообщение "same", если обе строки кодируют обследование одной и той же сети метро, или сообщение "different", если исследованные сети метро являются различными.

2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

same
different