Drzewo i mrówki

Limit pamięci: 6 MB

Informatycy lubią drzewa. Mrówki także lubią drzewa. Niech więc będzie dane drzewo, po którym chodzą dwie mrówki - Lewa Mrówka i Prawa Mrówka - w sposób pokazany na powyższym rysunku (po ścieżce oznaczonej kropkowaną linią). Rozpoczynają one swoją wędrówkę na początku pnia, po przeciwnych jego stronach. Lewa Mrówka pokonuje każdą krawędź drzewa w czasie dwóch sekund, idąc od korzenia (w górę), a w czasie jednej sekundy, idąc w kierunku korzenia (w dół). Prawa Mrówka jest od niej dwa razy szybsza. W momencie, gdy mrówki spotykają się, obydwie zawracają. Jeśli któraś z nich zejdzie z drzewa na ziemię, natychmiast zaczyna wchodzić na drugą stronę pnia. Poza tym mrówki są tak malutkie, że nawet mikroskop nie wystarczyłby do ich zobaczenia (na rysunku celowo zostały powiększone). Twoim zadaniem jest napisanie programu, który obliczy, po jakim czasie mrówki zawrócą po raz drugi.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę zestawów testowych opisanych w dalszej części wejścia.

Opis każdego zestawu składa się z dwóch wierszy. W pierwszym z nich znajduje się parzysta liczba () oznaczająca liczbę krawędzi drzewa. W drugim wierszu znajduje się opis drzewa. Jest to napis długości reprezentujący liczbę binarną -bitową zapisaną w systemie szesnastkowym (przy użyciu cyfr oraz małych liter od a do f). Liczba ta opisuje, jak wygląda obejście całego drzewa przez Lewą Mrówkę przy założeniu, że Prawa Mrówka stoi w miejscu. Kolejne bity tej liczby (od lewej) oznaczają, czy idąc po kolejnych krawędziach na swojej ścieżce, Lewa Mrówka oddala się od korzenia (bit 1), czy też zbliża się do korzenia (bit 0). Drzewo posiada pień, tzn. dokładnie jedna krawędź wychodzi z korzenia drzewa.

Rozmiar żadnego pliku wejściowego nie przekroczy 50 MB. Uwaga: to jest istotnie więcej niż rozmiar pamięci dostępnej dla Twojego programu.

Wyjście

Twój program powinien wypisać wierszy z odpowiedziami dla kolejnych zestawów testowych. Odpowiedzią dla zestawu jest czas w sekundach, po którym mrówki zawrócą po raz drugi, wypisany jako nieskracalny ułamek p/q (bez spacji wokół /), gdzie i to liczby całkowite dodatnie. Jeśli odpowiedź jest liczbą całkowitą, to oczywiście .

Przykład

Dla danych wejściowych:

1
28
fb1da30d1b7230

poprawną odpowiedzią jest:

282/5

Przykład odpowiada rysunkowi, a ciąg bitów wygląda następująco:

1111 1011 0001 1101 1010 0011 0000 1101 0001 1011 0111 0010 0011 0000

Autor zadania: Szymon Acedański.