Koogle
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
각종 프로그래밍 대회에서 두각을 나타내던 Astein 은 최근 IT 업계에서 최고라고 평가 받는 Koogle 에 입사하게 되었다. Koogle 은 특히 사내 보안에 대해서 매우 엄격한 보안 규칙을 적용하기로 유명하다. 그 대표적인 예로, Koogle 은 신입 사원에게 사내에서 사용할 비밀번호를 굉장히 특이한 방식으로 부여한다. 아이디의 경우 제약이 없으나, 비밀 번호의 경우 사원이 임의로 결정하는 것이 아닌 사내에 존재하는 암호 사전 중에서 하나를 사용하여야 한다. 암호 사전에 들어있는 암호들은 알파벳 소문자와 숫자들의 조합으로 구성되어 있는데, 상당히 긴 편이고, 외우기도 어렵다. Astein 은 암호를 결정하려고 암호 사전을 살펴 보다가, 암호의 세기를 수치화 해서 표현한 다음 이 중에서 가장 센 암호를 사용하기로 마음먹었다.
임의의 암호 문자열 x 가 영문 소문자 A 글자와 숫자 B 글자를 포함하고 있다고 할 때, x 의 세기는 다음과 같이 정의된다.
Strength(x) = 26^A * 10^B예를 들어, x="ab1e4" 일 경우, Strength(x)=26^3 * 10^2 = 1757600 이다.
Astein 은 이러한 공식을 세우고 손으로 이를 계산하고자 하였는데, 계산을 통해 나오는 값이 매우 커서 계산하기가 어려웠다. 더군다나 회사에 출근한 첫날이기 때문에 Astein 의 컴퓨터에는 아무런 프로그램도 깔려 있지 않았으며, Astein 이 처음 깐 프로그램은 Astein 이 즐겨 쓰는 Mate on 메신저와 게임 Nabimogi 가 전부였다. 메신저에 접속한 Astein 은 친구이자 Astein 만큼 프로그래밍 대회에서 두각을 나타내는 당신에게 암호의 세기를 비교하기 위한 프로그램을 작성해달라고 이야기 하였다. Astein 은 "지금부터 3시간 동안 Nabimogi 를 할터이니 답을 내놓아라" 고 이야기를 하고 Nabimogi 를 하러 갔다. 3시간이 지나서도 답을 내놓지 못할 경우, 불쌍한 Astein 은 회사에서 잘릴지도 모른다! 재빨리 Astein 이 원하는 프로그램을 짜주자!
입력
입력의 첫번째 줄에는 테스트 케이스의 개수 C (1 <= C <= 50) 가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 암호 사전에 포함된 암호 후보의 수 N (1 <= N <= 100) 이 주어지고, 그 후 N 줄에 암호 사전에 포함된 암호들이 주어진다. 모든 암호는 알파벳 소문자와 숫자로만 구성되어 있으며, 그 길이는 1,000 이하이다.
출력
각 테스트 케이스에 대해서 세기가 가장 큰 암호를 출력한다. 만약 세기가 가장 큰 암호가 여러 개 있을 경우 사전 순으로 가장 빠른 암호를 선택하라. 사전에서 숫자는 영문 소문자 보다 앞에 등장한다.
예제 입력
2 3 abc 012 a01 3 cdf cde fdb
예제 출력
abc cde
노트
