로드 시리즈

돈(Don)과 잰(Jan)은 도로 위에서 함께 많은 시간을 보내며, 심심함을 달래려고 로드 시리즈(Road Series)라는 게임을 한다. 목표는 어떤 표지판에서 숫자 1을 찾고, 그다음 2, 그다음 3, ...을 차례로 찾는 것이다. 여러 자리 숫자는 그 자릿수들이 표지판에서 서로 바로 붙어 있어야 하며, 하나의 표지판이 여러 개의 숫자를 제공할 수 있다.

예를 들어 678-43 15라고 적힌 표지판에서는 $67$, $78$, $43$, $15$를 쓸 수 있지만, $84$(두 자리 사이에 붙임표가 있음)나 $31$(두 자리 사이에 공백이 있음)은 쓸 수 없다. 또한 한 자리 숫자 $6$, $7$, $8$, $4$, $3$, $1$, $5$와 세 자리 숫자 $678$도 쓸 수 있다. 일반적으로, 어떤 숫자는 그 자릿수들이 표지판 글자 안에서 끊기지 않고 연속으로 나타날 때에만 그 표지판에서 사용할 수 있다.

숫자를 반드시 순서대로만 찾도록 하면 게임이 너무 느려서, 규칙을 다음과 같이 완화했다. $n$을 마지막 완성 숫자라고 하자. 이는 $1$부터 $n$까지의 모든 숫자를 이미 찾은, 가장 큰 값이다. (처음에는 마지막 완성 숫자가 $0$이다.) 또한 이미 본 숫자가 $n$보다 너무 크지 않으면 기억해 둘 수 있게 했다. 구체적으로, 고정된 창 크기 $w$에 대해 $n + w$ 이하인 범위(창) 안에서 본 숫자는 기억할 수 있다. 어떤 숫자를 볼 때 그 값이 $n + w$보다 크면 그 숫자는 기억되지 않는다.

예를 들어 $w = 4$이고 마지막 완성 숫자가 $19$라고 하자. 그러면 $23$까지의 숫자를 기억할 수 있다. Show time at 8:25, no one under 21 admitted라는 표지판에서는 $21$은 쓸 수 있지만 $25$는 쓸 수 없다($23$을 넘기 때문이다). 이어지는 표지판이 The FleaBag Hotel, phone 555-2520이라면, 여기 있는 $20$ 덕분에 $20$이 완성되고, 이미 기억해 둔 $21$도 완성되어 마지막 완성 숫자가 $21$이 된다. 이제 창이 $25$까지 닿고, $25$가 바로 그 같은 표지판에도 나타나므로 $25$ 역시 쓸 수 있다.

첫 번째 줄에는 테스트 케이스의 수 $m$이 주어진다. 각 테스트 케이스는 두 양의 정수 $k$와 $w$가 있는 줄로 시작한다. 여기서 $k$($k \le 1000$)는 표지판의 개수, $w$($w \le 100$)는 창 크기이다. 그다음 $k$개의 줄에 각각 표지판 하나의 글자가 주어진다. 표지판의 글자는 영숫자, 문장 부호, 공백이 임의로 섞여 있을 수 있으며, 길이는 최대 $1000$이다.

각 테스트 케이스마다 한 줄을 Case i: n h 형식으로 출력한다. 여기서 $i$는 $1$부터 시작하는 테스트 케이스 번호, $n$은 그 테스트 케이스의 표지판들로 얻을 수 있는 마지막 완성 숫자, $h$는 창 안에서 여전히 기억하고 있는 가장 큰 숫자이다($n$을 넘는 숫자를 아무것도 기억하고 있지 않으면 $h$는 $n$과 같다).