Have you ever cooked something? No? Not a problem! Whenever you try to cook something, you need some ingredients, obviously with some water, oil and heat. May be finally you will manage to cook the dish you wanted. But I am not sure if you will dare to taste it! π
Here, you are given some ingredients, you need to tell me how many different recipes are possible from the ingredients? Ingredients will be given as a string S consisting of digits (0-9) where each digit is an ingredient. A recipe is a mixture of some unique ingredients. So, you need to pick up exactly D ingredients from the ingredients in string S to make a recipe. Also, there is a restriction that you canβt use β0β as the first ingredient of a recipe. And keep in mind β240β and β420β are different recipes.
Now, can you tell me how many recipes you can make using D ingredients from the ingredients given in string S?
The first line will contain T (1 β€ T β€ 100), denotes the number of test cases. Next T lines will contain a string S (1 β€ |S| β€ 10), which holds the ingredients and no ingredient will come more than once, and D (1 β€ D β€ |S|) .
Print the number of possible recipes.
Input | Output |
---|---|
2 1235 3 490 2 | 24 4 |