모래뱀상어

모래뱀상어는 한 배에 새끼 한 마리만 낳는다. 어미는 알을 자궁에 품고, 알은 자궁 안에서 부화하며, 가장 큰 배아가 형제를 하나씩 먹어 치워 결국 한 마리만 남는다. 생물학에서는 이를 자궁 내 동족 포식이라고 부른다. 가장 큰 배아에게는 좋은 전략이지만 나머지에게는 그렇지 않다. 이길 수 없는 배아는 최대한 오래 버티는 쪽을 노리고, 당신은 그런 배아 한 마리의 전략을 세운다.

배아는 $n$마리이고 크기는 모두 다르다. 하루는 다음과 같이 진행된다.

하루가 시작될 때 살아 있는 배아를 크기가 큰 순서로 줄 세운다. 크기가 같으면 입력에서 먼저 나온 배아가 앞선다. 이 순위는 하루 동안 고정된다. 배아가 차례를 받는 순서도 이 순위와 같고, 하루가 진행되면서 크기가 바뀌어도 순위를 다시 계산하지 않는다.

차례가 왔을 때 아직 살아 있는 배아는 다른 배아 한 마리를 먹는다. 당신을 뺀 모든 배아는 자기보다 순위가 낮으면서 살아 있는 배아 중 가장 앞선 배아, 즉 자기보다 작은 배아 중 가장 큰 배아를 먹는다. 자기보다 순위가 낮은 배아가 하나도 살아 있지 않으면 아무것도 먹지 않는다. 당신은 자기 차례에 순위가 낮고 살아 있는 배아 중 아무나 한 마리를 먹을 수 있고, 아무것도 먹지 않을 수도 있다. 자기보다 순위가 높은 배아는 절대 먹을 수 없다. 어떤 배아가 다른 배아를 먹으면 먹은 쪽의 크기는 두 크기의 합이 되고 먹힌 쪽은 사라진다. 죽은 배아는 차례가 와도 아무것도 하지 않는다.

당신이 처음에 다섯 번째로 큰 배아라고 하자. 가장 큰 배아가 두 번째로 큰 배아를 먹어 크기가 둘의 합이 된다. 두 번째 배아는 죽었으므로 차례를 그냥 넘기고, 세 번째 배아가 네 번째 배아를 먹는다. 그다음이 당신 차례다. 모든 배아가 차례를 한 번씩 지나면 하루가 끝나고, 다음 날은 살아남은 배아의 크기로 순위를 새로 정해 다시 시작한다.

가장 큰 배아는 계속 가장 큰 배아로 남으므로 당신은 어떻게 하든 언젠가 먹힌다. 날짜는 1일부터 센다. 최대한 오래 버티도록 먹을 상대를 골랐을 때 당신이 먹히는 날을 구하라.

첫 줄에 데이터 집합의 개수 $K$가 주어진다 ($1 \le K \le 100$). 각 데이터 집합은 두 줄이다. 첫 줄에 정수 $n$과 $m$이 주어진다 ($2 \le n \le 50$, $2 \le m \le n$). $n$은 배아의 수이고, $m$은 전략을 세우는 대상이 몇 번째 배아인지를 나타낸다. 둘째 줄에 정수 $n$개 $s_1, s_2, \dots, s_n$이 주어지고 $10^6 > s_1 > s_2 > \dots > s_n \ge 0$을 만족한다. $s_i$는 $i$번째 배아의 크기다. 당신은 크기가 $s_m$인 배아다.

각 데이터 집합마다 Data Set x:를 한 줄에 출력한다. $x$는 1부터 시작하는 데이터 집합 번호다. 다음 줄에 최적 전략을 따를 때 $m$번째 배아가 먹히는 날을 출력한다. 각 데이터 집합 뒤에 빈 줄을 하나 출력한다.