Time Limit: 3s
Memory Limit: 128MB
피츌리아는 K대에 다니는 새내기이다. 이미 코딩을 완벽하게 마스터한 피츌리아는 컴퓨터 프로그래밍 수업시간이 무척이나 지루했고, 시간을 보낼 무언가가 필요했다.
그러던 어느 날, 정말 심심했던 피츌리아는 자신의 학번 뒤 6자리인 102564 를 곱하면서 놀고있었다. 그러다가 문득 놀라운 사실을 발견했다!
102564에 4를 곱하면 102564 × 4 = 410256 으로, 처음 숫자에서 가장 오른쪽 숫자를 가장 왼쪽에 붙여놓은 것이랑 똑같아졌다! 이런 성질을 만족하는 또다른 숫자를 찾아보던 피츌리아는 128205 도 128205 × 4 = 512820 가 됨을 알아내었다. 이 역시 가장 오른쪽 숫자 5를 12820의 왼쪽이 붙여놓은 수랑 같아졌다.
피츌리아는 이런 마법같은 성질을 가진 숫자들이 더 없을까 궁금해졌다. 들으라는 수업은 안듣고...n과 k가 주어졌을 때, 가장 오른쪽의 수가 k이면서, n을 곱한 결과물이 원래 수의 가장 오른쪽자리 수를 왼쪽에 붙여놓은 것이랑 똑같아지는 수 중 최소값을 찾아보자.
첫째줄에는 테스트케이스의 수 t가 주어진다.
그 다음 각 t개의 줄마다 2개의 숫자 n과 k (1 ≤ n ≤ 9, 1 ≤ k ≤ 9)가 주어진다.
각 테스트케이스마다 한줄에 하나씩 구하려는 수를 출력한다. 만약 그런 수가 존재하지 않는다면 0을 출력한다.
2 4 5 2 1
128205 0
n=6, k=9인 경우 정답의 앞부분을 보면 152542372881355932203... 이고, 이는64bit integer로도 표현이 불가능한 수이다.