팰린드롬 덧셈

팰린드롬이란 거꾸로 읽어도 제대로 읽는 것과 같은 수를 의미한다.

예를 들어, 10진법 수 0, 3, 77, 12321는 모두 팰린드롬이다. 다만, 10진법 수 10, 610는 팰린드롬이 아니다. 어떤 수가 팰린드롬인지 그 여부를 따질 때에는 Leading zeros를 생각하지 않기로 하자.

팰린드롬이 아닌 7진법 수 610를 보자. 이는 팰린드롬인 7진법 수 535, 33, 6의 합으로 표현할 수 있다.

이처럼 B진법의 N자리 수 K가 주어질 때, 이를 팰린드롬인 B진법 수 세 개의 합으로 표현하는 프로그램을 작성하시오.

총 T개의 테스트 케이스가 입력으로 주어진다.

각 테스트 케이스마다 하나의 줄에 B와 K가 사이에 공백을 두고 주어진다.

각 테스트 케이스마다 하나의 줄에 답을 출력한다.

만약, B진법 수 K를 팰린드롬인 B진법 수 세 개의 합으로 표현할 수 없다면, "-1"(따옴표 제외)를 출력한다.

만일 표현할 수 있다면, 그 세 개의 수를 사이에 공백을 두고 출력한다. 세 개의 수는 모두 음이 아닌 올바른 B진법 수여야 하며, Leading zero가 있어서는 안된다.

모든 입력 데이터는 아래의 조건을 모두 만족한다.

• 1 ≤ T ≤ 2.5 × 105
• 5 ≤ B ≤ 62
• K는 올바른 B진법 양수다. 즉, 각 자릿수는 0 이상 B 미만이며 Leading zero를 포함하지 않는다.
• 모든 테스트 케이스의 N의 합은 106을 넘지 않는다.

충분히 큰 진법에 대하여, 아래의 숫자를 10진법의 수로 변환하면 다음과 같다:

• 0 = 0(10)
• 9 = 9(10)
• A = 10(10)
• Z = 35(10)
• a = 36(10)
• z = 61(10)