#P1018. 毕业旅行

毕业旅行

"当一个故事要结束的时候,我们总会想起它的开始,就像是,一切回到了从前。"

令 f(x)f(x) 为正整数 xx 十进制表示下的最大数码。例如,f(4523)=5f(4523)=5 以及 f(1001)=1f(1001)=1。

这是艾莉第一次踏上 ICPC 亚洲区域赛赛场时遇到的签到题——原题给定四个正整数 la,ra,lb,rbl_a, r_a, l_b, r_b(满足 la≤ral_a \le r_a 且 lb≤rbl_b \le r_b),求 f(a+b)f(a+b) 的最大值,其中 la≤a≤ral_a \le a \le r_a 且 lb≤b≤rbl_b \le b \le r_b。

转眼间,距离他开启 ACM 生涯,已经过去了整整三年。如今的他,早已能轻松解决这类入门题目。于是,他决定给这道承载着回忆的题目加点新意。

具体地说,给定两个正整数 l,rl, r,满足 l≤x≤rl \le x \le r,你需要:

  1. 求出 f(x)f(x) 的最大值。
  2. 在所有能够令 f(x)f(x) 取得最大值的 xx 中,将 xx 转换为不含前导零的字符串 sxs_x 后,求出字典序最小的 sxs_x。

称长度为 xx 的字符串 P=p1p2⋯pxP = p_1p_2\cdots p_x 的字典序小于长度为 yy 的字符串 Q=q1q2⋯qyQ = q_1q_2\cdots q_y,若:

  • x<yx < y 且对于所有 1≤i≤x1 \le i \le x 有 pi=qip_i = q_i;或者
  • 存在一个整数 1≤t≤min⁡(x,y)1 \le t \le \min(x, y),对于所有 1≤i<t1 \le i < t 有 pi=qip_i = q_i,且 pt<qtp_t < q_t。

Input

每个测试文件含有多组测试数据。

第一行输入一个整数 TT(1≤T≤1051 \le T \le 10^5)表示测试数据组数。对于每组测试数据:

唯一的一行输入 22 个整数 l,rl, r(1≤l≤r≤1091 \le l \le r \le 10^9)。

Output

每组数据输出一行两个整数,分别表示 f(x)f(x) 的最大值和在取到 f(x)f(x) 的最大值时的字典序最小的 sxs_x。

4
11 17
8 39
5 27
1 2
7 17
9 19
9 19
2 2