즉흥 여행

상일이는 여행을 즉흥적으로 떠난다. 한 번의 여정은 다음과 같이 진행된다.

1. 지금 있는 도시의 공항으로 간다.
2. 그 공항에서 출발하는 항공편 가운데 티켓 한 장을 무작위로 산다. 각 항공편을 고를 확률은 모두 같다.
3. 산 티켓의 항공편을 타고 다른 도시로 간다.

한 번의 여행은 정확히 $K$번의 여정으로 이루어지고, 출발 공항은 언제나 ICN이다. 출발하는 항공편이 하나도 없는 공항도 있어서, 그런 공항에 도착하면 여정을 더 이어갈 수 없다.

여행 코스는 $K$번의 여정 동안 상일이가 지나는 공항을 순서대로 적은 것이다. 코스의 확률은 각 여정에서 그 항공편을 고를 확률을 모두 곱한 값이다. $K$번의 여정을 모두 마치는 코스 가운데 확률이 가장 높은 코스의 마지막 공항을 구하라. 그런 코스는 항상 존재한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스의 첫째 줄에 공항의 수 $N$과 한 번의 여행에서 해야 하는 여정의 수 $K$가 주어진다. ($2 \le N \le 100$, $1 \le K \le 1000$)

다음 $N$개 줄에는 각 공항의 IATA 코드가 한 줄에 하나씩 주어진다. 코드는 알파벳 대문자 세 글자로 이루어지고 서로 다르며, 이 가운데 하나는 ICN이다.

다음 $N$개 줄에는 각 줄에 $N$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수 $S_{ij}$는 $i$번 공항에서 출발해 $j$번 공항에 도착하는 항공편의 수이다. ($0 \le S_{ij} \le 100$, $S_{ii} = 0$) $i$번 공항에서 출발하는 항공편은 모두 $S_{i1} + S_{i2} + \dots + S_{iN}$편이므로, 상일이가 $i$번 공항에서 $j$번 공항으로 갈 확률은 $S_{ij}$를 이 합으로 나눈 값이다.

각 테스트 케이스마다 확률이 가장 높은 여행 코스의 마지막 공항의 IATA 코드를 한 줄에 출력한다. 확률이 가장 높은 코스가 여럿이고 마지막 공항이 서로 다르면, 그 공항의 코드 가운데 사전순으로 가장 앞선 것을 출력한다.