Under construction

Still being built. Things may change

Classical A+B Problem

Time limit4sMemory limit1024 MB

Summary
Given a number n written as a sum of two repdigits, the task is to output any such pair of repdigits a and b.
Level

Easy3 of 10

Topics
Math, Implementation, Brute force
Solved
No attempts yet

Statement

An integer is called a repdigit if it is positive and its decimal representation consists of repeated instances of the same digit. For example, 11, 666666, 44444444, and 999999999999 are repdigits, while 00, 4424444244, 5021650216, and 787788787788 are not.

You are given a positive integer nn. It is known that nn can be represented as n=a+bn = a + b, where aa and bb are repdigits. Find any such representation.

Input

The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). Each test case is a single line containing an integer nn without leading zeros (2≤n<1040002 \le n < 10^{4000}). It is guaranteed that nn can be represented as n=a+bn = a + b, where aa and bb are repdigits. The total number of digits in nn over all test cases does not exceed 10510^5.

Output

For each test case, print two integers aa and bb such that n=a+bn = a + b and both aa and bb are repdigits. If there are multiple solutions, print any of them.

Examples1

  1. Example 1

    Input
    6
    2
    786
    1332
    89110
    2333333
    10000000000000000000000000001
    
    Expected output
    1 1
    777 9
    333 999
    88888 222
    2222222 111111
    9999999999999999999999999999 2