喜欢字符串的东东哥

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

题目描述

ACM集训队的东东哥最喜欢字符串了，以至于经常秒解各类字符串的大题，今天他又做了一道字符串的题，并把它抛给了菜菜k，菜菜k太菜了所以找到了你，你能帮他AC这道题吗？

给定一个主串p,和n个模式串 $s_1,s_2,...,s_n$ 。定义f(a,b)函数为字符串b在字符串a中出现的次数。现在需要求 $\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(p, s_i + s_j)$ 的值。换一种说法就是对于给定的n个模式串，你需要计算出任意两个模式串(包括自己和自己)拼接起来的字符串在主串p中出现的次数的和。

$s_i+s_j$ 表示第i个模式串和第j个模式串前后相接，例如"ab"+"cd"="abcd".

输入描述:

第一行输入一个正整数T代表有T组数据
对于每组数据第一行输入字符串p,
第二行输入一个正整数n
接下来n行每行一个字符串代表.
1<=|p|<=10000,1<=n<=1000,,保证。代表模式串的长度。

输出描述:

对于每组数据输出一个正整数,代表答案

示例1

输入

复制

2
aaabacaa
2
a
aa
aaabacaa
4
a
a
a
b

输出

复制

5
33

说明

。