Programowanie i algorytmy

Rekurencja ćwiczenia

Ćwiczenie 1. Napisz program, który wyświetli n kolejnych wyrazów ciągu zdefiniowanego następująco:

{tex}a_n= \left\{\begin{matrix} 2,& dla \: n = 1\\ a_{n-1}*2, & dla \: n\: nieparzystego\\ a_{n-1}+2, & dla\: n\: parzystego \end{matrix}\right.{/tex}.

Ćwiczenie 2. Dla podanego ciągu liczb całkowitych wypisz ten ciąg w odwrotnej kolejności.

Ćwiczenie 3. Zrealizuj algorytm Euklidesa metodą rekurencyjną.

Ćwiczenie 4. Zrealizuj algorytm przeszukiwania binarnego metodą rekurencyjną.

Ćwiczenie 5. Napisz program, który zamieni liczbę zapisaną w systemie dziesiętnym na system szesnastkowy.

Ćwiczenie 6. Warcaby klasyczne.

Zadanie to można rozwiązać na automatycznej sprawdzarce na stronach: 

 

Bitek jest początkującym warcabistą. Grywa od czasu do czasu partie ze swoim wójem Bajtosławem. Niestety zdarzy mu się wykonać nieprawidłowy ruch polegający na zbiciu niemaksymalnej ilości pionów, przez co często traci szansę na wygraną. Jako zaprzyjaźniony programista, napisz program, który określi ile pionów nasz gracz powinien zbić.

Rozpatrujemy sytuację, w której ruch należy do przeciwnika z białymi pionami. Gracz ten posiada tylko pionki (bez damek).

Input

W pierwszym wierszu dodatnia liczba naturalna t < 100001, określająca ilość zestawów danych.

Każdy zestaw składa się z dwóch wierszy. Pierwszy wiersz określa położenie pionów białych, drugi czerwonych.

Każdy wiersz ma następującą specyfikację:

najpierw jedna liczba naturalna n, taka, że 1 <= n <=12, określająca liczbę pionów na planszy, następnie n pionów oddzielanych pojedynczą spacją. Każdy pion posiada dwie informacje w postaci:

jedna litera od a do h określająca numer kolumny oraz liczba od 1 do 8, określająca numer wiersza danego pionka.

Plansza na początku gry wygląda następująco:

warcaby

 

Output

Dla każdego zestawu jedna liczba, określająca liczbę pionów do zbicia.

Example

Input:


2
2 b2 c3
4 d4 b6 d6 f6
1 a1
7 b2 d4 d6 b6 d2 f2 b4

Output:


3
7

Uwaga!!! Zanim zaczniesz rozwiązywać zadanie, koniecznie zapoznaj się z zasadami gry w warcaby klasyczne.

 

Rozwiązania do ćwiczeń - musisz być zalogowany