Peptydy

Kapitan Mambeks przeprowadza badania peptydów. Peptydy mają nadane unikalne nazwy, złożone z cyfr oraz dużych i małych liter (bez polskich liter). W nazwach rozróżnana jest wielkość liter. Peptydy składają się z sekwencji aminokwasów. Każdy aminokwas opisany jest za pomocą jednego znaku, którym jest cyfra, duża lub mała litera (bez polskich liter), przy czym rozróżniana jest wielkość liter. Przykładowa sekwencja aminokwasów tworzacych peptyd może mieć postać: AbA1AC7b. Kapitan w swoich badaniach musi pogrupować peptydy tak, aby było spełnione jedno z założeń:

  1. W jednej grupie znajdują się peptydy zawierające identyczne aminokwasy. Jako przykład można podać peptydy AbA1AC7b i b77C1bA.
  2. W jednej grupie znajdują się peptydy zawierające identyczne aminokwasy oraz liczba wystąpień każdego z nich we wszystkich peptydach jest taka sama. Założenia tego nie spełnia przykład podany w punkcie 1, gdyż w pierwszym peptydzie aminokwas oznaczony symbolem 7 występuje tylko jeden raz, natomiast w drugim peptydzie występuje on dwa razy. Nie spełnia także założenia liczebność aminokwasu typu A.

Twoim zadaniem jest napisane programu, który dla zadanego zestawu peptydów pogrupuje je w taki sposób, aby spełnione było założenie 1 lub 2. Każda grupa powinna zawierać co najmniej dwa peptydy.

Dane wejściowe:

W pierwszym wierszu zapisana jest liczba N, będąca liczbą zestawów danych wejściowych. W kolejnych wierszach jest zapisanych N zestawów danych wejściowych.

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą K (1 ≤ K ≤ 1000) określającą liczbę peptydów. Kolejnych K wierszy zawiera opisy peptydów. Opis pojedyńczego peptydu zawiera jego nazwę oraz ciąg aminokwasów, które go tworzą. Nazwa peptydu oraz ciąg aminokwasów oddzielone są od siebie znakiem ":". Peptyd zawiera maksymalnie 200 aminokwasów a jego nazwa złożona jest maksymalnie z dwóch znaków.

Dane wyjściowe:

Dla każdego zestawu danych wejściowych program ma wypisać grupy peptydów. Peptydy należące do jednej grupy powinny być wypisane w jednym wierszu w kolejnosci w jakiej występują w danych wejściowych. Ich nazwy powinny być oddzielone znakiem "," (występuje on także na końcu wiersza). Peptydy w grupie porównywane są względem pierwszego peptydu i w przypadku kiedy dla danego peptydu spełnione jest tylko założenie 1, to jego nazwę należy poprzedzić gwiazdką. Grupy należy wypisać w kolejności w jakiej wystepują w danych wejściowych pierwsze peptydy każdej z grup. Podział na grupy dla pojedynczego zestawu danych zakończony jest wierszem zawierającym pojedynczy znak "#".

Przykładowe dane wejściowe:

3
9
C:baaac
c:abaca
H:AAABBBCCCCaaaabbc
a4:ABCABC
E:abac
d:cabaa
A:aacb
1y:cabBAC
F:AaBbCc
5
PP:asdfsdgfg
B:asdfasdfa
pp:dfghjkl
D:asdfasdfa
E:dfghlkj
5
K:fpfjher
M:FPFHJWWER
77:FPFJHEWRW
P:FPFJHER
z9:FFPFJHRE
	

Przykładowe dane wyjściowe:

C,c,*E,d,*A,
c,*E,d,*A,
H,*1y,*F,
E,*d,A,
d,*A,
1y,F,
#
B,D,
pp,E,
#
M,77,
P,*z9,
#