Метро

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

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

Входные данные

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

В каждой строке закодировано одно корректное обследование сети метро.

Выходные данные

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