LIDS
We all know about LIS ( Longest Increasing Sub sequence). The task to find the length of the longest increasing sub sequence in a given array of integers is very easy. For example, the length of the LIS for { 15, 27, 14, 38, 26, 55, 46, 65, 85 } is 6 and the longest increasing sub sequence is {15, 27, 38, 55, 65, 85}. But, do we all know about LIDS? The task to find the length of the longest increasing digit sub sequence within an integer is known as LIDS. For example, length of LIDS for 1234 is 4, length of LIDS for 12234 is 4, length of LIDS for 456123 is 3. {7}, {1,4,9} , {5,9} are some valid increasing digit sequence while {3,2} , {1,1} , {4, 9 , 1} are invalid.
You are given two integer x and y. You have to answer Maximum Length of LIDS between x and y inclusive and the number of different ways Maximum LIDS can be formed. Two ways are considered different if the Longest Increasing Digit Sequence are not same or they are chosen from different position in an integer.
Input
Input starts with an integer T (≤ 10000) , denoting the number of test cases. Each of the test cases consists of two space separated integers x and y denoting the range.
Easy Subtask: 1 ≤x ≤y <1000 Medium Subtask: 1≤x≤y≤1000,000,000 and (y-x) ≤1000 Hard Subtask: 1≤x≤y≤1000,000,000 Digits are : 0,1,2,3,4,5,6,7,8 and 9.
Output
For each of the test cases, you need to print one line of output. The output for each test case starts with the test case number, followed by Maximum Length of LIDS and the number of ways LIDS can be formed. You must output as it is given in the sample output section.
Sample
For First Sample, Length LIDS of 111 is 1 and LDIS is {1}Length LIDS of 112 is 2 and LIDS is {1, 2}Length LIDS of 113 is 2 and LIDS is {1, 3}Length LIDS of 114 is 2 and LIDS is{1,4}So, Maximum Length of LIDS is 2. And It can be formed in 6 ways. For Second Sample, There is exactly one number. Length LIDS of 15432 is 2. We can see, there are four different possible solutions.They are : {1, 5} , {1, 4}, {1, 3} and {1, 2}