Start: 2023-10-11 09:00:00

1012赛前模拟赛08

End: 2023-10-18 15:00:00
Now  2026-09-20 05:32:38  类型: IOI  状态: Ended 

P1. 统计子序列
Description

作为字符串属性的魔法师,小R有一件史诗级法宝——字符串S 作为小R的粉丝,小P努力修炼,深入险境,只为获得和小R类似的法宝,经过数十年的积累,小P获 得了n个字符串,现在小P想知道,这n个字符串有多少个在S中出现。

请你帮他统计一下一个字符串t在S中出现,是指t为S的一个子序列

Input

第一行一个字符串S 

第二行一个正整数n 

接下来n行,每行一个字符串c[i] 

Output

一行一个整数表示答案 

Examples

Input

abcde
4
a
bb
acd
ace

Output

3

Input

babaaaa
5
abaaab
aaaaaaa
aa
aaaaaaa
ab

Output

2

Input

a
1
a

Output

1
Hint

对于20%的数据: |S|<=50000,n<=200 

对于50%的数据: |S|<=50000,n<=2000 

对于100%的数据: |S|<=50000,n<=5000,|c[i]|<=50

Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit