Oznaczenie 1:
P(X) - rodzina wszystkich możliwych podzbiorów zbioru X.

Definicja 1:
σ-algebrą podzbiorów zbioru Y lub, krócej, σ-algebrą w Y nazywamy rodzinę X Ì P(Y) spełniającą następujące warunki:

1. Ø Î X
2. Dla każdego A Î X: Y \ A Î X
3. Dla każdego ciągu (A_n) w X: suma A_nÎ X

Definicja 2:
Najmniejszą σ-algebrę w zbiorze Y zawierającą rodzinę A Ì P(Y) nazywamy σ-algebrą generowaną przez A i oznaczamy σ(A).

Zatem σ(A) jest σ-algebrą w Y taką, że:

1. A Ì σ(A)
2. Jeśli C jest σ-algebrą w Y i A Ì C, to σ(A) Ì C

Zadanie
Niech Y będzie zbiorem liczb naturalnych mniejszych, lub równych n {1,2,3,...,n}. Mając daną rodzinę A Ì P(Y) wyznacz ilość zbiorów w rodzinie σ(A) będącej σ-algebrą generowaną przez rodzinę A, wiedząc, że rodzina A składa się ze zbiorów rozłącznych.

Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita, oznaczająca liczbę zestawów danych, które za chwilę pojawią się na wejściu. W pierwszym wierszu zestawu znajduje się liczba n (0<=n<=10000) określającą zbiór Y (Y = {1,2,3,...,n}). W kolejnym wierszu znajduje się opis rodziny A, która jest zapisana w postaci kolejnych zbiorów, które do niej należą. Każdy zbiór jest zawarty w klamry {}, a każdy element zbioru jest oddzielony przecinkiem. Również każdy zbiór jest oddzielony przecinkiem. Każdy ze znaków rozdzielających jest otoczony spacjami. Opis rodziny kończy się zbiorem pustym oznaczonym { }.

Wyjście
Program powinien podać liczbę zbiorów w rodzinie σ(A).

Przykład

wejście:
4
1
{ 1 } , { }
999
{ }
5
{ 1 , 2 } , { 3 } , { 4 } , { }
9
{ 7 , 6 , 2 , 1 } , { 8 , 5 , 3 } , { }

wyjście:
2
2
16
8