W galaktyce IC 1101 z gwiazdozbioru Węża, oddalonej 1.07 bilionów lat świetlnych od Ziemi, istnieje dużo różnych form życia. Część z nich uznano za inteligentne. Każda z inteligentnych form żyje na różnej liczbie planet. Niestety, w galaktyce nie został jeszcze dopracowany system pocztowy. Nie ustalono kodów pocztowych jakie należy wypełnić na druczkach, aby przesyłka trafiła na konkretną planetę. Aby zestandaryzować adresy dla systemu pocztowego, Główny Imperator zarządził spis wszystkich planet, na których znajdują się inteligentne formy życia.
Każda z planet może zostać jednoznacznie określona za pomocą trzech współrzędnych względem centrum galaktyki. Jednostkami używanymi w galaktyce IC 1101 są lata świetlne. Imperator poprosił prezydentów każdej z inteligentnych form o przysłanie współrzędnych wszystkich planet gdzie egzystują. Różne formy posiadają różną liczbę odnóży i palców, w związku z tym obliczają w różnych systemach, a nie tak jak ludzie w systemie dziesiętnym. Dlatego też każda forma przysłała współrzędne planet wyrażone w swoim systemie liczenia. Aby raz na zawsze rozwiązać problem różnych systemów liczenia oraz by umożliwić szybką analizę adresu przez komputery ustalono, że systemem w którym będzie wyrażony kod pocztowy będzie system dwójkowy. Natomiast kod pocztowy planety będzie się składał z zapisu trzech współrzędnych określających położenie planety względem centrum galaktyki. Ustalono, że kod pocztowy będzie miał postać trzech oddzielonych od siebie pustych miejsc na cyfry oraz jednego znaku określającego czy dana wartość jest ujemna czy dodatnia.
Wiedząc, że formy lubią kolonizować sąsiednie planety, przyszłościowo zdecydowano, że współrzędne planet zostaną zaokrąglone do następnej wartości z ich systemu liczenia reprezentowanej przez cyfrę 1 i następnie same zera. To znaczy: jeżeli planeta posiada jedną ze współrzędnych wyrażoną w systemie dziesiętnym 78910, to zostanie zaokrąglona do wartości 100010. Analogicznie w systemie ósemkowym wartość 777778 zostanie zaokrąglona do 1000008. Wartość 10005 zostanie zaokrąglona do 100005.
Twoim zadaniem jest ustalić ile miejsc na cyfry 0/1 trzeba przygotować na druczkach, według powyższych ustaleń Imperatora tak, aby nie zabrakło miejsca na współrzędne dla każdej z planet w galaktyce. Imperator przekazał Ci pozycje wszystkich planet oraz system liczenia w jakim są wyrażone.
Wejście
Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1 ≤ N ≤ 20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:
Jeden zestaw danych
Pierwszy wiersz zestawu danych zawiera liczbę całkowitą n (1 <= n <= 104) oznaczająca liczbę planet w całej galaktyce. W kolejnych n wierszach znajdują się opisy planet. Każdy z takich opisów składa się z czterech liczb całkowitych si, xi, yi, zi (2 <= si <= 4096, 1 <= xi; yi; zi <= 10109), oddzielonych pojedynczymi białymi spacjami, oznaczających odpowiednio system liczbowy w jakim wyrażone są współrzędne oraz współrzędne x, y, z planety. Współrzędne są reprezentowane w następującej formie: po znaku + lub - znajdują się znaki opisujące liczbę. Dla systemów liczenia o podstawie poniżej 11 używane są zwykłe cyfry. Dla systemów liczenia o podstawie powyżej 10 do 36 włącznie używane są dodatkowo duże litery alfabetu łacińskiego (bez polskich znaków diakrytycznych), np: 1F, GX, A7ACM3LYX. Dla systemów liczenia od 37 do 362 używane są dwa znaki do wyrażenia jednej cyfry. Dla systemów liczenia od (362 + 1) do 4096 używane są trzy znaki do wyrażenia jednej cyfry. Liczby oznaczające współrzędne są bez nieznaczących zer na początku, a ilość znaków składających się na reprezentację liczby jest nie większa niż 220.
Wyjście
Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu są trzy liczby całkowite oddzielone spacją, oznaczające liczbę miejsc na cyfry potrzebne do zapisania współrzędnych dowolnej planety odpowiednio dla współrzędnej x, y, z.
Przykład
Dane wejściowe
3
2
5 +13 +4 +2
8 +756 +42 +3245
7
27 +1M2C3456G789H012NN3456O78A90CE12F -PA123E4D512C3A4 +E1F2A3C1E2G3
35 -X123A45G678E9J0N1T23R45A67L8903O -12EA22X2E2 +3EE3333EE333EE3333EE333EE333
31 -T123E45A67C890A1234H56E78J +11 -1E205FE82TA
70 +AABBCCDDEEFFGGHHAABBCCDDEEFFGGHH -AABBCC -AABBCCDDEEFF
61 +AABBCCDDEEFFGGHH0ABBCCDDEEFFGGHHAABB +AABBCC -AABBCCDDEEFFGGHH
71 -A23BBB333 +A32B37F35AAA122 +A33A55A44AEE
16 +FF -EEEEEEEEFFFFFFAAAAFFAAAA -AAAAAAAAAAA33BB33BBBCCCC
2
13 +BABA -212341AA -1000
53 -7A -3X6Y +100000
Wynik
10 7 13
165 97 144
15 30 18
