Nancy's Birthday

Nancy's Birthday

---

Time Limit:1s	Memory limit:32M
Accepted Submit:12	Total Submit:65

---

Description

Nancy has bought a lottery. The lottery numbers are positive integers. The prized lottery numbers are determined by randomizing two integers m and k (m>=0, k>=1). Any lottery number that contains m 0's can be prized, and the kth number is the first prize if all the prized numbers are sorted in an ascending order. Nancy won the first prize with a lucky number, for the number of digits and the leftmost digit in the first prized number happen to make up the date of Nancy's birthday. Can you work out Nancy's birthday?

Input

The first line in the input is an integer N representing the number of test cases. The following N lines are N test cases. Each line contains two integers separated by one space , where the first integer is m and the second is k (0<=m<=10，1<=k<=10^12).

Output

For each test case, output a line containing two integers separated by one space, where the first integer is the number of digits in the first prized number and the second integer is the leftmost digit in the first prized number.

Sample Input

2
1 5
2 15  

Output for the Sample Input

2 5
4 1

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

#define size 30

long long power9[size + 1];
long long C[size + 1][size + 1];

int main()
{
    long long i, j, k, tmp, test;
    long long t1,t2;

    power9[0] = 1;
    for (i = 1; i <= size; ++i)
        power9[i] = power9[i - 1] * 9;

    for (i = 0; i <= size; ++i)
    {
        for (j = 0; j <= i; ++j)
        {
            tmp = 1;
            if ((i != 0) && (j != 0))
            {
                for (k = j + 1; k <= i; ++k)
                    tmp *= k;
                for (k = 1; k <= i - j; ++k)
                    tmp /= k;
            }
            C[i][j] = tmp;
        }
    }

    cin >> test;
    for(i = 0;i < test;i ++)
    {
        cin >> t1 >> t2;
        for (j = t1;; ++j)
        {
            if(9 * power9[j - t1] * C[j][t1] >= t2)
                break;
            else
                t2 -= (9 * power9[j - t1] * C[j][t1]);
        }
        cout << j + 1 << ' ' << (t2 - 1) / (power9[j - t1] * C[j][t1]) + 1 << endl;
    }
    return 1;
}