동굴 탐험

「open sesame!」가 성공한 뒤 알리바바는 다른 작물들도 여러 가지로 실험했다. 대부분은 특별한 일이 없었다. 그러다 어느 날 「open sugarcane!」이라고 외치자 바위 하나가 밀려나며 이상한 동굴의 입구가 드러났다.

동굴은 여러 개의 방으로 이루어져 있었다. 입구는 곧장 방 하나로 이어졌는데, 이 방을 시작 방이라고 부르자. 일부 방 쌍은 단방향 터널로 연결되어 있었다. 터널은 세 종류 중 하나다. 어떤 터널은 abrasive 벽을 가졌고, 어떤 터널은 battered 벽을 가졌으며, 나머지는 calcified 벽을 가졌다. 짐작했겠지만 터널 종류는 a, b, c로 표기한다.

방마다 들어오는 터널과 나가는 터널이 얼마든지 많을 수 있다. 같은 종류의 터널이 여러 개 있어도 되고, 터널이 하나도 없어도 된다. 같은 방에서 시작해 같은 방으로 끝나는 터널도 있을 수 있다.

방 4개와 터널 8개로 이루어진 동굴의 예시.

단방향 터널이 있는 동굴을 혼자 탐험하는 것은 그리 좋은 생각이 아니다. 다행히 알리바바는 필요하면 마흔 명의 도둑(그리고 그들의 무한히 많은 친구들)의 도움을 받을 수 있다. 한 번의 동굴 탐험은 다음과 같이 진행된다.

1. 알리바바가 터널 종류의 유한한(비어 있을 수도 있는) 수열, 즉 문자열을 고른다.
2. 도둑들이 한 명씩 차례로 다음 절차를 반복한다.
   1. 도둑은 긴 밧줄의 한쪽 끝을 허리에 묶는다.
   2. 시작 방에 들어선다.
   3. 알리바바가 고른 종류의 수열과 정확히 일치하고, 이전 도둑들이 (전체 경로로) 지나간 적이 없는 터널 경로를 따라가려고 한다.
   4. 성공하면 도둑은 걸어서 도착한 마지막 방에서 기다린다. (각 방은 그곳에서 걸음을 마친 도둑을 모두 수용할 만큼 넓다고 가정한다.)
3. 도둑이 임무를 수행할 수 없게 되면(가능한 터널 수열이 모두 이미 누군가에 의해 지나간 상태이면), 탐험 한 회차가 끝난다. 마지막으로 실패한 도둑은 밧줄로 끌어내어 동굴 밖으로 빼낸다.

이 순간 도둑이 적어도 한 명 있는 방들의 집합을 생각하자. 이 집합을 유의 집합이라고 부른다. (유의 집합이 공집합일 수도 있다.)

4. 알리바바가 밧줄을 이용해 모든 도둑을 동굴 밖으로 끌어낸다.

1단계에서 고르는 수열에 따라 유의 집합이 달라질 수 있다. 위의 예시 동굴을 보자. 알리바바가 ac를 고르면 유의 집합 $\{2, 3\}$을 얻는다. 한 도둑은 0 → 3 → 2로 가고, 다른 두 도둑은 0 → 1 → 3으로 가는데, 1에서 3으로 갈 때는 각자 다른 터널을 쓴다. bcb는 유의 집합 $\{3\}$을, 빈 수열은 $\{0\}$을, ccc는 빈 유의 집합을 만든다.

입력 파일의 첫 줄에는 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.

각 테스트 케이스는 정수 $n$과 $d$가 적힌 한 줄로 이루어진다.

테스트 케이스마다 출력은 두 가지 중 하나다.

주어진 $n$과 $d$에 맞는 동굴이 존재하면, 동굴 하나를 터널의 나열로 출력한다. 첫 줄에는 동굴의 터널 수 $m \le 5000$을 출력한다. (유효한 동굴이 있다면 항상 터널이 5000개보다 훨씬 적은 동굴이 존재한다.) 이어지는 $m$개의 줄에는 「x y z」 형식으로 터널을 한 줄에 하나씩 출력한다. 여기서 $x$는 터널이 출발하는 방, $y$는 터널이 도착하는 방, $z$는 $a$, $b$, $c$ 중 하나다. 방은 0부터 $n - 1$까지 번호가 매겨지며, 0번 방이 시작 방이다.

그런 동굴이 없으면 정수 -1 하나를 한 줄로 출력한다.

추가 공백을 출력해도 된다. (예시 출력은 보기 좋게 공백을 넣었다.)

첫 번째 테스트 케이스에서 만든 동굴의 유의 집합은 세 가지다. 공집합, $\{0\}$, $\{1\}$.

두 번째 테스트 케이스의 답은 앞 페이지에 나온 동굴이다.

세 번째 테스트 케이스에는 그런 동굴이 없다는 것이 분명하다.