# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Cook a Dish

By AnikaTahsin · Limits 1s, 512 MB

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?

## Input

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|) .

## Output

Print the number of possible recipes.

## Sample

InputOutput
```2
1235 3
490 2```
```24
4
```

### Statistics

78% Solution Ratio

Gulam_KibriaEarliest, 5M ago

Gulam_KibriaFastest, 0.0s

Gulam_KibriaLightest, 0 B

mdvirusShortest, 162B