题目描述

给定一个字符串 $s$ 和一个字符串 $t$，请你求出：$s$ 有多少对前缀后缀对 $(x, y)$，使得 $yx$ 等于 $t$。

形式化的，设 $n$ 是字符串 $s$ 的长度，你要求出有多少对 $(i, j)$ 满足 $1 \leq i, j \leq n$ 使得 $s_{j}s_{j+1}\dots s_ns_1s_2\dots s_i = t$。

其中 $s_i$ 表示 $s$ 的第 $i$ 个字符，字符串下标从 $1$ 开始。

输入格式

本题单个测试点内有多组测试数据。输入的第一行是一个整数，表示数据组数 $T$。

对每组数据，按如下格式输入：
第一行是一个字符串，表示 $s$。
第二行是一个字符串，表示 $t$。

输出格式

对每组数据，输出一行一个整数表示答案。

1
aabaabaabaab
aabaabaab

2

提示

数据规模与约定

• 对 $10\%$ 的数据，$|t| = 1$。
• 对 $40\%$ 的数据，$|s| \leq 100$。
• 对 $70\%$ 的数据，$|s| \leq 10^4$。
• 对 $100\%$ 的数据，$1 \leq |s| \leq 10^5$，$1 \leq |t| \leq 100$，$1 \leq T \leq 10$，输入字符串仅含小写字母。