D. Largest Digit
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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$$$.

Input

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

The first and only 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

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

Example
Input
2
178 182 83 85
2 5 3 6
Output
7
9
Note

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

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