Problem Description

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$ satisfying $l_a \le r_a$ and $l_b \le r_b$, compute the maximum possible value of $f(a + b)$, where $l_a \le a \le r_a$ and $l_b \le b \le r_b$.

Input Format

There are multiple testdata. The first line contains an integer $T$ ($1 \le T \le 10^3$), denoting the number of test cases. For each test case:

The first line contains four integers $l_a$, $r_a$, $l_b$, and $r_b$ ($1 \le l_a \le r_a \le 10^9$, $1 \le l_b \le r_b \le 10^9$).

Output Format

For each test case, output one integer per line, representing the maximum value of $f(a + b)$.

2
178 182 83 85
2 5 3 6

7
9

Hint

For the first sample testdata, the answer is $f(182 + 85) = f(267) = 7$.

For the second sample testdata, the answer is $f(4 + 5) = f(9) = 9$.

Translated by ChatGPT 5