Farmer Jiang is so slim that his cows really want to make themselves much slimmer than Farmer Jiang. But first of all, they must know the actual weight of themselves.
On the edge of the farm, there is a wierd weight scale near the fence. The result of the scaling is encrypted such that neither Farmer Jiang nor other cows cannot read out the exact weight. When a cow steps on the weight scale, the screen shows a string consists of non-capital letters, and a key number k. The weight scale, however, is old-fashioned and Bessie the smartest cow figured out that each distinct letter appearing in the string is corresponding to a unique digit. Moreover, the key number k means that among all possible outcomes, the actual weight is the k-th smallest one.
Now Bessie the cow wants to help other cows get their weight. Please help Bessie.
There are multiple test cases and the first line contains an integer T<=100 indicating the total number of test cases. For each test case, there is a line containing a string S and an integer k. The length of S is no greater than 10000, and the number of distinct digits appears in a single string will always be less or equal to 10. Note that the first digit cannot be decrypted as zero.
For each tset case, please output the actual weight. You may assume there always exist an answer for all test cases.
4 abcdefghij 1 jiabcdfghe 1 ac 2 abdefg 3
1023456789 1023456789 12 102347
Migrated from old NTUJ.
Tmt
| No. | Testdata Range | Score |
|---|