외계인 진법 변환

어떤 행성의 외계인은 손가락이 열여섯 개여서, 열여섯 개의 숫자(작은 것부터 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F)로 수를 적습니다. 우리가 쓰는 십진법과 마찬가지로 수는 숫자의 나열로 적으며, 그 값은 다음 규칙으로 정해집니다.

• 한 자리 수의 값은 그 숫자의 값입니다.
• 어떤 수 b 뒤에 숫자 d를 붙여 만든 수의 값은, b의 값에 고정된 밑을 곱한 뒤 d의 값을 더한 것입니다. 십진법에서는 밑이 십이고, 손가락이 열여섯 개인 외계인에게는 밑이 십육입니다.

다른 행성의 외계인들은 손가락 개수가 서로 다릅니다. 이들은 수를 적는 규칙은 같지만 저마다 다른 밑을 사용합니다.

이 외계인들이 서로 소통할 수 있도록, 한 외계인이 적은 수를 다른 외계인이 이해할 수 있는 수로 바꾸는 프로그램을 작성하세요.

첫째 줄에 뒤따르는 테스트 케이스의 개수를 나타내는 정수 하나가 주어집니다.

각 테스트 케이스는 한 줄에 세 값 x, y, z로 이루어집니다. x와 y는 십진법으로 적힌, 두 외계인이 사용하는 밑이며 각각 $2$ 이상 $36$ 이하입니다. 수 z는 밑 x로 적혀 있고, 숫자 0-9와 값 10부터 35를 나타내는 대문자 A-Z를 사용합니다. z의 값은 사십억 이하입니다.

각 테스트 케이스마다, z와 값이 같지만 밑 y로 적은 수를 한 줄에 출력하세요.

숫자 0-9와 (값 10부터 35를 나타내는) 대문자 A-Z를 사용하고, 앞에 0을 붙이지 않습니다(값이 0이면 0 한 글자로 적습니다).