gogo40 contest (2015/01)

Wszyscy pewnie znacie problem wież Hanoi (jeśli nie, to zaleca się wcześniej z nim zapoznać: Wieże z Hanoi na Wikipedii). W tym zadaniu trochę go zmodyfikujemy. Standardowo mamy trzy pałeczki o numerach kolejno: 1, 2, 3. Wprowadźmy dodatkowe ograniczenie mobilności krążków. Krążki o numerach nieparzystych można przenosić jedynie zgodnie ze wskazówkami zegara: 1->2->3->1, zaś krążki o parzystych numerach - tylko przeciwnie: 1->3->2->1. Pozostałe reguły przenosin są bez zmian. Napisz program, który dla danej liczby n krążków oraz dla danych liczb s, d oznaczających kolejno pałeczkę początkową i końcową wypisze serię ruchów (pod uwagę bierzemy tylko optymalną ilość przenosin) po której wszystkie krążki z pałeczki s znajdą się na pałeczce d w żądanej kolejności.

Input

W pierwszym wierszu wejścia znajduje się liczba 1 <= t <= 25 oznaczająca ilość przypadków testowych. Każdy przypadek testowy składa się z trzech liczb: n, s, d ( 1 <= n <= 20; 1 <= s,d <= 3; s jest różne od d ) oznaczających kolejno: liczbę krążków, numer pałeczki startowej i numer pałeczki końcowej.

Output

Dla każdego przypadku testowego wypisz serię ruchów (dozwolonych według wyżej wymienionych zasad oraz zasad ogólnych problemu), która będzie optymalna i doprowadzi do przeniesienia wszystkich krążków z pałeczki startowej na pałeczkę końcową. Każdy ruch powinien być postaci:

numer_krazka: skad->dokad

co oznacza: krążek o numerze numer_krazka przenosimy z pałeczki o numerze skad na pałeczkę o numerze dokad.

każdy ruch w osobnej linii.

po każdym teście odstęp nowej linii.

Example

Input:
3
1 1 3
2 2 3
2 3 1

Output:
1: 1->2
1: 2->3

1: 2->3
2: 2->1
1: 3->1
1: 1->2
2: 1->3
1: 2->3

1: 3->1
2: 3->2
1: 1->2
1: 2->3
2: 2->1
1: 3->1