Sparing w Programowaniu Zespołowym UAM & PP, 6.11.2004

Opis

Problem wieży hanoi jest następujący: N krążków o różnych rozmiarach znajduje się na pierwszym palu (im wyżej tym mniejsze). Należy, zgodnie z regułami gry (tj. można przekładać jednocześnie po 1 krążku i nigdy krążek większy nie może leżeć na mniejszym), przemieścić je na drugi pal, wspierając się trzecim palem. Buddyjscy mnisi poszli w końcu po rozum do głowy i doszli do wniosku, że koniec świata, który miał nastąpić po przeniesieniu wszystkich krążków z pierwszego palika na drugi pal, może nie wypalić. Stwierdzili więc, iż zamiast przekładać 1 krążek na raz, ułatwią sobie i będą przekładali większą liczbę krążków na raz... Zakładając, że jeden ruch (przełożenie pewnej liczby (przylegających) krążków z jednego pala na drugi) trwa 1 sekundę, powiedz wędrowcze, po ilu sekundach nastąpi koniec świata?

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się liczba D, oznaczająca liczbe testów opisanych w kolejnych liniach. Opis każdego testu składa się z dwóch liczb całkowitych: N (0 ≤ N ≤ 32), oznaczająca liczbę krążków znajdujących się na pierwszym palu oraz K (0 ≤ K ≤ 32), oznaczająca maksymalną liczbę krążków, jaką mnisi mogą przenieść w jednym ruchu.

Specyfikacja wyjścia

Dla każdego zestawu testowego wypisz w osobnej linii liczbę sekund, która jest potrzebna do przeniesienia całej wieży Hanoi z pierwszego pala na trzeci. Jeżeli wieża nigdy nie zostanie przeniesiona wypisz słowo NIE.

Przykład

3
2 0
2 1
2 2

NIE
3
1