Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

math

number theory

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. GCD Length

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given three integers $$$a$$$, $$$b$$$ and $$$c$$$.

Find two positive integers $$$x$$$ and $$$y$$$ ($$$x > 0$$$, $$$y > 0$$$) such that:

- the decimal representation of $$$x$$$ without leading zeroes consists of $$$a$$$ digits;
- the decimal representation of $$$y$$$ without leading zeroes consists of $$$b$$$ digits;
- the decimal representation of $$$gcd(x, y)$$$ without leading zeroes consists of $$$c$$$ digits.

$$$gcd(x, y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.

Output $$$x$$$ and $$$y$$$. If there are multiple answers, output any of them.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 285$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b \le 9$$$, $$$1 \le c \le min(a, b)$$$) — the required lengths of the numbers.

It can be shown that the answer exists for all testcases under the given constraints.

Additional constraint on the input: all testcases are different.

Output

For each testcase print two positive integers — $$$x$$$ and $$$y$$$ ($$$x > 0$$$, $$$y > 0$$$) such that

- the decimal representation of $$$x$$$ without leading zeroes consists of $$$a$$$ digits;
- the decimal representation of $$$y$$$ without leading zeroes consists of $$$b$$$ digits;
- the decimal representation of $$$gcd(x, y)$$$ without leading zeroes consists of $$$c$$$ digits.

Example

Input

4 2 3 1 2 2 2 6 6 2 1 1 1

Output

11 492 13 26 140133 160776 1 1

Note

In the example:

- $$$gcd(11, 492) = 1$$$
- $$$gcd(13, 26) = 13$$$
- $$$gcd(140133, 160776) = 21$$$
- $$$gcd(1, 1) = 1$$$

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2023 19:07:43 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|