Wstęp do programowania w C++

Napisz program, który określi jakie przeniesienia krążków należy wykonać, aby przenieść wszystkie n krążków z pierwszego palika na trzeci zachowując zasady problemu.

Zasady:

1. Krążki prznosimy pojedynczo.
2. Nie wolno położyć większego krążka na mniejszy
3. Należy przenieść wszystkie krążki z pierwszego palika na trzeci
4. Mnimalna liczba ruchów do przeniesienia n krążków jest równa 2ⁿ - 1

Input

Pierwsza liczba t < 20 określa ilość zestawów danych

Każdy zestaw składa się z jednej liczby 1<n<16 określający ilość krążków do przeniesienia.

Output

Dla każdego zestawu zdefiniowane ruchy potrzebne do przeniesienia krążków w optymalny sposób.

Example

Input:
1

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