码丁实验室，一站式儿童编程学习产品，寻地方代理合作共赢，微信联系：leon121393608。
【题目描述】
令$F(A,B)$ 表示选择一个串 的非空前缀$A$ 和串$B$ 的非空后缀 使得将串$S$ 和串$T$ 拼接起来之后是回文串的方案数。
现在给定两个串$A$ 和$B$ ，令$A_i$ 表示串$A$ 的第$i$ 长的后缀，$B_i$ 为串$B$ 的第$i$ 长的前缀。
有$Q$ 组询问，第$i$ 组询问给定$x_i$ 和$y_i$ ，对每组询问求$F(A_{x_i}，B_{y_i})$ 的值。
【输入】
第一行一个字符串$str$ ，表示数据类型。
接下来的两行分别表示字符串$A$ 和$B$ 。
接下来一行一个正整数$Q$ ，表示询问的个数。
接下来$Q$ 行，每行两个正整数$x_i$ 和 $y_i$。
【输出】
输出$Q$ 行，每行一个整数，表示这一组询问的答案。
【输入样例】
B newionyzz wyxioiwen 1 1 1
【输出样例】
16
【提示】
【样例解释】
对于样例 1，共有以下 $16$ 种方案：
${S=n,T=n};{S=n,T=en};{S=ne,T=n};{S=ne,T=en}$；
${S=ne,T=wen};{S=new,T=en};{S=new,T=wen};{S=new,T=iwen}$；
${S=new,T=ioiwen};{S=newi,T=wen};{S=newi,T=iwen};{S=newi,T=oiwen}$；
${S=newio,T=iwen};{S=newio,T=oiwen};{S=newio,T=ioiwen};{S=newion,T=oiwen}$
【数据规模】
对于100%的数据，字符串中只出现小写字母。
| 子任务编号 | 子任务分值 | $max(|A|,|B|)$ | $Q$ | 数据类型 |
| $1$ | $10$ | $≤40$ | $≤200$ | $C$ |
| $2$ | $15$ | $≤2000$ | $≤2000$ | $A$ |
| $3$ | $7$ | $≤10^5$ | $=1$ | $C$ |
| $4$ | $19$ | $≤2000$ | $≤2000$ | $C$ |
| $5$ | $20$ | $≤8×10^5$ | $≤10^5$ | $B$ |
| $6$ | $26$ | $≤8×10^5$ | $≤10^5$ | $C$ |
| $7$ | $3$ | $≤8×10^5$ | $≤10^5$ | $C$ |
数据类型，$A$ ：数据随机；$B$ ：串 随机且$|B|≤10^4$ ；$C$ ：无特殊性质。