Counting Distinct Subsequences

You are given a string (s) consisting of lowercase Latin letters and an integer (k). Your task is to determine the number of distinct subsequences of (s) that have exactly length (k). A subsequence is a sequence that can be derived from (s) by deleting zero or more characters without changing the order of the remaining characters. For example, if (s = \texttt{abc}) and (k = 2), the distinct subsequences are (\texttt{ab}), (\texttt{ac}) and (\texttt{bc}). Note that even if there are multiple ways to form the same subsequence (especially when characters repeat), it should only be counted once.

Input/Output Specifications:

• Input is read from the standard input (stdin).
• Output is written to the standard output (stdout).

inputFormat

The first line of input contains an integer (T) representing the number of test cases. Each of the following (T) lines contains a test case, which consists of a string (s) and an integer (k) separated by a space.

outputFormat

For each test case, output a single line containing the number of distinct subsequences of (s) that have length (k).## sample

3
abc 2
abcd 3
abcdef 3

3
4
20