Distinct Problem Names

In ION programming contests, each year a special lowercase letter string is designated as that year’s naming string. Every problem name must be a non‐empty contiguous substring of the year’s naming string. Moreover, a new problem name must not be identical to any problem name (i.e. any non‐empty contiguous substring) used in the previous year.

Little A has been chosen to prepare the problems for ION2018. Although he does not know the actual names chosen in ION2017, he managed to obtain the naming string for ION2017. Now he has Q queries. In each query you are given two strings:

• The ION2017 naming string s.
• The ION2018 naming string t.

Your task is to count, for each query, how many distinct non-empty contiguous substrings of t (i.e. candidate problem names for ION2018) are guaranteed not to be equal to any contiguous substring of s (i.e. any problem name from ION2017).

Note: Since in ION the problem names of a year are chosen as some contiguous substrings of that year’s naming string, the invalid names for ION2018 are exactly all the distinct non-empty substrings of s.

Formally, for each query, let F(X) be the set of all distinct non-empty contiguous substrings of string X. You need to compute the number of strings in F(t) - F(s).

Input Format:

Q
s_1
t_1
s_2
t_2
...
s_Q
t_Q

Output Format:

ans_1
ans_2
...
ans_Q

Constraints: The strings consist only of lowercase letters. It is guaranteed that for every query, the string given for ION2017 (s) is a contiguous substring of some (unspecified) string.

Explanation:

• For example, if s = "a" and t = "ab", then
  F(t) = {"a", "b", "ab"} and F(s) = {"a"}.
  The valid names are {"b", "ab"}, so the answer is 2.
• If s = "abc" and t = "ab", then F(t) = {"a", "b", "ab"} and F(s) contains all of these, so the answer is 0.

Hint: An efficient way to count distinct substrings is to use a suffix automaton. You may build the suffix automata for s and t and use them to compute the number of distinct substrings in each string, as well as the number of substrings common to both.

inputFormat

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

For each query, the next two lines contain a string s (the ION2017 naming string) and a string t (the ION2018 naming string), respectively.

outputFormat

For each query, output a single integer on a new line -- the count of valid problem names for ION2018.

sample

3
a
ab
abc
ab
abab
baba

2
0
1

</p>