该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

众所周知，雪豹和小冀是最卷的两位同学，雪豹有一个字符串 $T$。小冀有若干个字符串 $S_1,S_2,\dots,S_n$。雪豹想知道，对于小冀的每一个字符串中，最多有多少个子串是和 $T$ 循环同构的。

对于一个字符串 $a$，每次把 $a$ 的第一个字符移动到最后一个，如果操作若干次后能够得到字符串 $b$，则 $a$ 和 $b$ 循环同构。所有字符都是小写英文字母

输入格式

第一行一个字符串 $T \:(|T| \leq 10^6)$，其中 $|T|$ 为字符串 $T$ 的长度

第二行一个正整数 $n \: (n \leq 1000)$ 接下来 $n$ 行为 $S_1 \sim S_n \: (|S_1|+|S_2|+\dots+|S_n| \leq 10^7)，max(|S_1|,|S_2|,|S_3|,|S_4|,\dots,|S_n|) \leq 10^6$

输出格式

输出 $1$ 行表示每个串的答案

输入输出样例

abab
2
abababab
ababcbaba

5

提示

样例中第一个字符串共有 $5$ 个子串与 $T$ 循环同构，第二个字符串有两个，最终取最大值为 $5$.