시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB5821409822.791%

문제

7-세그먼트 디스플레이란 아래와 같이 7개의 선분으로 글자를 표시할 수 있는 장치를 말한다.

최근 시프트는 디지털 회로에 관한 강의를 듣고 있다. 시프트가 이번 주에 받은 과제의 내용은 아래와 같다.

7-세그먼트 디스플레이 n개를 사용한 회로를 구성한다. 양의 정수 m을 입력받아, n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 표시하시오.

다행히도 입출력은 강의자료에 전부 나와 있어서 그대로 따라 하면 됐기 때문에 별로 문제가 될 건 없었다. 더군다나, n자리 수로 만들 수 있는 가장 큰 m의 배수를 계산하는 건 너무 쉽다.

하지만 시프트는 놀라운 발견을 하게 되는데, 7-세그먼트 디스플레이 하나에는 0~9의 숫자뿐만 아니라 11도 표시할 수 있다는 사실이었다.

두 개의 7-세그먼트 디스플레이로 1을 표시하는 대신 한 개의 디스플레이로 11을 표시하면 한 자리를 아낄 수 있고, 이 방법으로 더 큰 m의 배수를 표현할 수 있을지도 모른다. 예를 들어 4자리 수 중 가장 큰 3의 배수는 9999이지만, 4개의 디스플레이로 만들 수 있는 가장 큰 3의 배수는  9   11   11   11 이다.

이 방법을 활용해, 정수 nm에 대해 시프트가 n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 출력하라.

입력

첫 번째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 25)

각 테스트 케이스는 한 줄로 이루어져 있으며, 두 개의 수 nm이 주어진다. (1 ≤ n ≤ 9, 1 ≤ m ≤ 105)

출력

각 테스트 케이스마다 n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 한 줄에 하나씩 출력한다. 가능한 가장 큰 값이 0일 경우, "0"(따옴표 제외)을 출력한다.

예제 입력 1

3
4 3
4 4
4 5

예제 출력 1

9111111
1111116
1111115

출처

University > 서강대학교 > 2019 Sogang Programming Contest > Master F번