题目描述

给定三个正整数 $M,N,k$，对于一个正整数 $x$，云浅认为它是「好数」当且仅当

• $M\le x\le N$；
• $x$ 在十进制下的所有位上的数字和为 $k$。

请你求出所有「好数」中，十进制下所有位上数字的积最大的那个。

你需要求出这个数并输出其十进制下所有位上数字的积。如果有多解，选尽可能小的 $x$。

数据保证有解。

输入描述

本题有多组数据。第一行一个正整数 $T$ 表示数据组数。

接下来 $T$ 行，每行三个正整数 $M,N,k$。

输出描述

对于每组数据，一行两个正整数，以空格隔开，分别表示你求出的 $x$ 以及其十进制下所有位上数字的积。

1
114514 191981 10

121222 16

【样例 1 说明】

取 $x=121222$，则其数字和为 $1+2+1+2+2+2=10$，数字积为 $1\times 2\times 1\times 2\times 2\times 2=16$

【数据范围】

对于 $100\%$的数据，$1\le M\le N\le 5\times 10^6,1\le k\le 100,1\le T\le 100$