장식용 울타리

리처드는 새 집을 막 완성했다. 이제 집에 부족한 것은 귀여운 나무 울타리 하나뿐이다. 나무 울타리를 어떻게 만드는지 몰랐던 그는 하나 주문하기로 했고, 우연히 귀여운 나무 울타리에 관한 결정판 자료인 《ACME 울타리 카탈로그 2002》를 손에 넣었다. 그 서문을 읽고 나서 그는 무엇이 나무 울타리를 귀엽게 만드는지 이미 알게 되었다.

나무 울타리는 $N$개의 나무 판자를 세로로 세워 한 줄로 나란히 붙여 만든다. 다음 두 조건을 모두 만족할 때, 그리고 그때에만 울타리는 귀엽다.

• 판자들의 길이가 서로 모두 다르며, 정확히 $1, 2, \dots, N$ 판자 길이 단위이다.
• 양옆에 이웃이 있는 각 판자는 두 이웃보다 모두 크거나, 두 이웃보다 모두 작다. (따라서 울타리의 윗변은 오르내림을 번갈아 반복한다.)

그러므로 $N$개의 판자로 이루어진 각 귀여운 울타리는, 모든 $i$($1 < i < N$)에 대해 $(a_i - a_{i-1}) \cdot (a_i - a_{i+1}) > 0$을 만족하는 $1, \dots, N$의 순열 $a_1, \dots, a_N$으로 유일하게 나타낼 수 있다. 역으로, 이러한 각 순열은 하나의 귀여운 울타리를 나타낸다.

$N$개의 판자로 만들 수 있는 서로 다른 귀여운 울타리는 매우 많다. 카탈로그에 순서를 부여하기 위해 판매 담당자는 다음과 같이 정렬하기로 했다. 울타리 $A$(순열 $a_1, \dots, a_N$)가 울타리 $B$(순열 $b_1, \dots, b_N$)보다 카탈로그에서 앞에 온다는 것은, 모든 $j < i$에 대해 $a_j = b_j$이고 $a_i < b_i$인 어떤 $i$가 존재한다는 것과 동치이다. (즉, 두 울타리에 대응하는 순열에서 값이 처음으로 달라지는 위치를 찾아 그 위치의 값을 비교한다.) $N$개의 판자로 만든 모든 귀여운 울타리에는 카탈로그에 나오는 순서대로 1부터 번호가 매겨지며, 이 번호를 그 울타리의 카탈로그 번호라고 한다.

카탈로그 번호 순으로 정렬된, $N = 4$개의 판자로 만든 모든 귀여운 울타리.

모든 귀여운 나무 울타리를 꼼꼼히 살펴본 뒤 리처드는 그중 몇 개를 주문했다. 각 울타리에 대해 그는 판자의 개수와 카탈로그 번호를 적어 두었다. 나중에 친구들을 만났을 때 주문한 울타리를 보여 주고 싶었지만, 카탈로그를 어딘가에 잃어버렸다. 그에게 남은 것은 메모뿐이다. 그의 울타리가 어떤 모양일지 알아내도록 도와주자.

입력의 첫 줄에는 데이터 집합의 개수 $K$ ($1 \le K \le 100$)가 주어진다. 이어서 $K$개의 줄이 주어지며, 각 줄은 하나의 데이터 집합을 나타낸다.

각 줄에는 공백으로 구분된 두 정수 $N$과 $C$ ($1 \le N \le 20$)가 주어진다. $N$은 울타리의 판자 개수이고, $C$는 그 울타리의 카탈로그 번호이다.

$N = 20$개의 판자로 만든 귀여운 울타리의 총 개수는 64비트 부호 있는 정수에 들어간다고 가정해도 된다. 또한 입력은 항상 올바르다고 가정해도 된다. 특히 $C$는 항상 1 이상이며, $N$개의 판자로 만든 귀여운 울타리의 총 개수를 넘지 않는다.

각 데이터 집합에 대해, 카탈로그에서 $N$개의 판자로 만든 $C$번째 울타리를 나타내는 한 줄을 출력한다. 더 정확히 말하면, 그 울타리가 순열 $a_1, \dots, a_N$으로 나타내어질 때, 해당 줄에는 수 $a_i$들을 올바른 순서대로 하나의 공백으로 구분하여 출력해야 한다.