410775: GYM104101 H Beautiful String

In this problem, the alphabet contains only the first $$$18$$$ lowercase Latin letters; that is, the alphabet has only the characters from $$$a$$$ to $$$r$$$.

In this problem, the string index starts from $$$1$$$.

$$$Hile$$$ has a string $$$s$$$. She thinks a string $$$t$$$ of $$$n$$$ distinct letters is a beautiful string if any of the following conditions are met:

• $$$t_1$$$ appears in the string $$$s$$$ and $$$t_i$$$ is lexicographically strictly greater than $$$t_{i - 1}$$$ for $$$2 \le i \le n$$$.

• All characters in the string $$$t$$$ appear in the string $$$s$$$.

$$$t_i\ (1 \le i \le n)$$$ means the $$$i$$$-th character in the string $$$t$$$.

Now $$$Hile$$$ wants you to calculate the number of beautiful strings.

The first line contains an integer $$$T\ (1\le T\le 2 \times 10^5)$$$ — the number of test cases.

Each test case is one line contains one string $$$s$$$ $$$(1 \le |s| \le 2\times 10^5)$$$ and one integer $$$n\ (1\le n \le 18)$$$ — the string $$$s$$$ and the length of string $$$t$$$.

It is guaranteed that $$$\sum{|s|} \le 2 \times 10^5$$$, $$$|s|$$$ means the length of the string $$$s$$$.

For each test case, output an integer — the number of beautiful strings.

2
a 2
ar 2

17
18

In the first testcase, the beautiful string $$$t$$$ are: $$$ab,\ ac,\ ad,\ ae,\ af,\ ag,\ ah,\ ai,\ aj,\ ak,\ al,\ am,\ an,\ ao,\ ap,\ aq,\ ar$$$.

In the second testcase, the beautiful string $$$t$$$ are: $$$ab,\ ac,\ ad,\ ae,\ af,\ ag,\ ah,\ ai,\ aj,\ ak,\ al,\ am,\ an,\ ao,\ ap,\ aq,\ ar,\ ra$$$.