给定三个正整数 M , N , k ,

对于一个正整数 x ,云浅认为它是「好数」:

当且仅当 M ≤x ≤N;

x 在十进制下的所有位上的数字和为 k 。

请你求出所有「好数」中,十进制下所有位上数字的积最大的那个。你需要求出这个数并输出其十进制下所有位上数字的积。如果有多解,选尽可能小的 x 。

数据保证有解。

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

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

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

【样例1 说明】

取 x=121222 ,则其数字和为 1+2+1+2+2+2=10 ,数字积为 1×2×1 ×2 ×2 ×2=16 。

【数据范围】

对于 100% 的数据, 1 ≤M ≤N ≤5 ×10^{6} , 1 ≤k ≤100,1 ≤T ≤100 。