"When a story is about to end, we always think back to its beginning, as if everything has returned to the start."

Let $f(x)$ be the largest digit in the decimal representation of a positive integer $x$. For example, $f(4523) = 5$ and $f(1001) = 1$. Given four positive integers $l_a, r_a, l_b,$ and $r_b$ such that $l_a \le r_a$ and $l_b \le r_b$, calculate the maximum value of $f(a + b)$, where $l_a \le a \le r_a$ and $l_b \le b \le r_b$.

Ellie remembers the "easy" problem she encountered the first time she stepped onto the ICPC Asia Regional contest floor. In the blink of an eye, three full years have passed since she began her ACM career. Today, she can easily solve such introductory problems. Therefore, she decided to add a new twist to this problem that holds so many memories.

Specifically, given two positive integers $l$ and $r$ such that $l \le x \le r$, you need to:

1. Find the maximum value of $f(x)$.
2. Find the lexicographically smallest string $s_x$ obtained by converting $x$ to a string without leading zeros, among all $x$ that achieve the maximum value of $f(x)$.

A string $P = p_1 p_2 \dots p_x$ of length $x$ is lexicographically smaller than a string $Q = q_1 q_2 \dots q_y$ of length $y$ if: $x < y$ and $p_i = q_i$ for all $1 \le i \le x$, or There exists an integer $1 \le t \le \min(x, y)$ such that $p_i = q_i$ for all $1 \le i < t$, and $p_t < q_t$.

Input

Each test file contains multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^5$), representing the number of test cases. For each test case:

The only line contains two integers $l$ and $r$ ($1 \le l \le r \le 10^9$).

Output

For each test case, output a single line containing two integers: the maximum value of $f(x)$ and the lexicographically smallest string $s_x$ among all $x$ that achieve this maximum value.

Examples

Input 1

4
11 17
8 39
5 27
1 2

Output 1

7 17
9 19
9 19
2 2