패션 경찰 (Small)

2016 코드 잼 월드 파이널이 너무 기대된 나머지 당신은 뉴욕으로 이사했다. 당신은 서로 다른 재킷 $J$벌($1$번부터 $J$번), 서로 다른 바지 $P$벌($1$번부터 $P$번), 서로 다른 셔츠 $S$벌($1$번부터 $S$번)을 가져왔다. 셔츠는 바지보다 적지 않고, 바지는 재킷보다 적지 않다($J \le P \le S$).

당신은 매일 재킷 한 벌, 바지 한 벌, 셔츠 한 벌을 골라 한 벌의 옷차림으로 입는다. 매일 밤 모든 옷을 빨기 때문에 모든 옷은 날마다 입을 수 있다.

뉴욕의 패션 경찰은 모든 사람이 매일 무엇을 입는지 지켜보고 기록한다. 똑같은 옷차림을 두 번 입은 사실이 들키면 당신은 곧바로 5번가의 패션 감옥으로 끌려가 강제로 스타일을 바꿔야 한다. 이것만은 반드시 피하고 싶다. 같은 두 옷의 조합을 모두 합쳐 $K$번보다 많이 입은 사실이 들켜도 곧바로 패션 감옥에 끌려간다. 조합이란 특정 재킷과 특정 바지, 특정 재킷과 특정 셔츠, 또는 특정 바지와 특정 셔츠를 함께 입은 것을 말한다. 예를 들어 옷차림 (재킷 1, 바지 2, 셔츠 3)과 (재킷 1, 바지 1, 셔츠 3)으로 이루어진 집합에서 조합 (재킷 1, 셔츠 3)은 두 번 나오고, 조합 (바지 1, 셔츠 3)은 한 번만 나온다.

하루에 한 벌의 옷차림을 입는다. 패션 감옥에 끌려가지 않고 버틸 수 있는 최대 일수를 구하고, 그동안 입을 옷차림 목록을 만들어라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지며, 각 테스트 케이스는 네 정수 $J$, $P$, $S$, $K$가 적힌 한 줄로 이루어진다.

제한

• $1 \le T \le 100$
• $1 \le J \le P \le S$
• $1 \le K \le 10$
• $S \le 3$

각 테스트 케이스마다 먼저 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 패션 감옥에 끌려가지 않고 버틸 수 있는 최대 일수이다. 이어서 y개의 줄을 출력하는데, 각 줄에는 하루 옷차림의 재킷, 바지, 셔츠 번호를 이 순서대로 세 정수로 출력한다.

옷차림 $(a_1, b_1, c_1)$이 옷차림 $(a_2, b_2, c_2)$보다 사전순으로 작다는 것은 재킷 번호를 먼저 비교하고, 같으면 바지 번호를, 그것도 같으면 셔츠 번호를 비교해서 더 작다는 뜻이다. 옷차림은 이 순서로 정렬해서 출력한다. 패션 감옥을 피하는 $y$벌의 옷차림 집합이 여러 개라면, 정렬한 목록을 앞에서부터 옷차림 단위로 비교했을 때 사전순으로 가장 작은 집합을 출력한다.

1번 케이스에서는 패션 경찰이 $K$를 10으로 너그럽게 정했지만 만들 수 있는 옷차림이 하나뿐이므로 패션 감옥을 피할 수 있는 날은 하루뿐이다.

2번 케이스에서는 다른 옷차림을 하나라도 더하면 패션 감옥에 끌려간다.

• 1 1 3을 더하면 조합 (재킷 1, 바지 1)을 2번보다 많이 입게 된다.
• 1 2 3을 더하면 조합 (재킷 1, 바지 2)를 2번보다 많이 입게 된다.

이 경우 옷차림 5벌로 이루어진 어떤 집합도 적어도 한 번은 규칙을 어긴다.

한 옷차림 안의 재킷, 바지, 셔츠 번호는 $J$, $P$, $S$처럼 감소하지 않는 순서일 필요가 없다.

3번 케이스에서는 재킷과 바지 조합이 하나뿐이라 계속 다시 입어야 하므로, 어떤 셔츠를 입든 서로 다른 옷차림을 $K = 2$벌보다 많이 만들 수 없다.

4번 케이스에서는 옷차림 1 1 3과 1 2 1로도 2일 동안 패션 감옥을 피할 수 있지만, 1 1 1과 1 2 2가 사전순으로 가장 작은 목록이므로 이 집합이 답이다.