#2049 카드 게임

2 s   128 MB  

Description

 

휘철이는 최근 열심히 문제를 풀 던 중 영감을 얻어 다음과 같은 카드 게임을 개발 했다. 규칙은 다음과 같다:

0 이상 9 이하의 숫자가 적혀있는 N개의 카드가 존재하고, 게임 시작 전에 N개의 카드를 적당히 섞어서 한 장씩 아래에서 위로 겹쳐서 놓는다.

그다음 위에서부터 아래로 카드를 한 장씩 집어가며, 테이블에 카드를 놓는데, 이 때 카드는 한 열로 배치가 되어야 하며, 새로운 카드를 놓을 경우 배치가 된 카드들의 맨 오른쪽이나, 맨 왼쪽에 놓아야 한다. 모든 카드에 대한 배치가 완료되면, 왼쪽부터 오른쪽으로 읽어서 나오는 숫자가 최종적으로 완성된 숫자이며, 이를 통해 만들 수 있는 숫자가 최소를 찾는 것이 목표이다. 단, 맨 왼쪽의 숫자가 절대로 0이 되어서는 안된다.

 

N개의 카드에 적힌 숫자들이 입력되었을 때, 이에 대해서 만들 수 있는 숫자의 최소값을 구하는 프로그램을 작성하라.

Input

입력의 첫 줄에는 테스트 케이스의 개수를 뜻하는 T가 입력된다. 그 다음 줄 부터 T개의 줄에는 문자열이 입력되며, 이는 한번의 게임에서 사용될 카드의 정보를 뜻한다. 각 문자열의 i번째 문자는 위에서 i번째로 쌓여있는 카드에 적힌 숫자를 뜻한다. 문자열의 길이는 최소 1자, 최대 50글자로 입력되며, 모든 카드의 숫자가 0인 경우는 입력되지 않는다.

Output

입력된 문자열에 대해서 조건에 맞게 숫자를 만들었을 때 나올 수 있는 최소값을 출력하라.

Sample Input

Sample Output

3
565
9876543210
8016352
556
1234567890
1086352