캬루

• 주어진 수에서 숫자 하나를 바꿔서 소수가 아닌 수로 만들어야 하는데, 이런 수를 n개를 만들어야 한다
• 방법이야 다양하겠지만, 쉽게 떠올릴수 있는 방법은, 모든 자릿수의 합이 3의 배수인 수는 3의 배수라는 점을 이용하는 것이다.
• 어느 자리의 숫자를 바꿔도 모든 자릿수의 합이 3의 배수가 되도록 만들수 있으니까, 이 방법만으로 3의 배수를 n개 이상 만들수 있다.
• 실수의 여지가 있는 것은, 만들어지는 수가 0 으로 시작하지 않도록 하는 부분과, p가 1자리 수일때는 3을 만들지 않도록 해야 하는 부분이다. 내 경우 후자의 처리는 모든 자릿수의 합이 9의 배수가 되게 만든다음, 약수는 3으로 써주는 방식으로 처리했다.

"""Solution code for "BOJ 31288. 캬루".

- Problem link: https://www.acmicpc.net/problem/31288
- Solution link: http://www.teferi.net/ps/problems/boj/31288

Tags: [ad hoc]
"""

import sys


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, P = sys.stdin.readline().split()  # pylint: disable=unused-variable
        digit_sum = sum(int(c) for c in P)
        for i, c in enumerate(P):
            x = (int(c) - digit_sum) % 9
            if x == 0:
                x = 9
            print(f'{P[:i]}{x}{P[i+1:]} 3')


if __name__ == '__main__':
    main()