H-Beautiful String_2022年浙大城市学院新生程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

In this problem, the alphabet contains only the first $18$ lowercase Latin letters, that is, the alphabet contains 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 string $t$ .

输入描述:

The first line contains an integer  --- the number of test cases.

Each test case is one line contains one string   and one integer  --- the string  and the length of string .

It is guaranteed that ,  means the length of the string .

输出描述:

For each test case, you have to output an integer --- the number of beautiful string .

示例1

输入

复制

2
a 2
ar 2

输出

复制

17
18

说明

In the first testcase, the beautiful string  are:.

In the second testcase, the beautiful string  are:.