Minimum Operations to Subsequence

Problem Statement:

You are given an integer q representing the number of queries. Each query consists of two strings, s and t. The task is to determine the minimum number of operations required to make t a subsequence of s. In this problem, an operation is defined as adding a missing character from t into s. However, if every unique character in t occurs at least once in s, then t can potentially be a subsequence of s (by rearranging or selecting letters without any insertion), and the answer is 0.


In other words, if there exists any character in t that does not appear in s, you must perform an operation for each distinct missing character. Otherwise, if all characters of t are present in s, then no operation is needed, and the answer is 0.

The relationship can be formally expressed as:

$$\text{answer} = \begin{cases}0, & \text{if } \forall c \in \text{unique}(t),\, c \in s \\ \#\{ c \in \text{unique}(t) : c \notin s \}, & \text{otherwise} \end{cases} $$

inputFormat

Input is read from standard input (stdin).

The first line contains an integer q, denoting the number of queries.

For each query, there are two lines:
- The first line contains the string s.
- The second line contains the string t.

Note: The strings may be empty.

outputFormat

For each query, output a single integer on a new line to standard output (stdout) representing the minimum number of operations required so that t becomes a subsequence of s.## sample

3
abc
acd
abbbc
bbbbc
xyz
yz

1
0
0

</p>