给你一个由英文小写字母组成的字符串 $S$。

一个由英文小写字母和 * 组成的字符串 $T$ 在满足以下条件时被认为与 $S$ 匹配：

• 可以通过将 $T$ 中的每个 * 替换为长度大于或等于 $0$ 的任意字符串来得到 $S$。

例如，a*b 与 ab、acb 和 aabb 匹配，但不与 abc 匹配。

如果满足以下条件，则认为匹配是唯一的：

• 只有一种可能的方法来替换 $T$ 中的每个 * 以得到 $S$。

例如，a*b*c 唯一匹配 abc 和 axbxc，但不唯一匹配 abbc。这是因为你可以将第一个 * 替换为 b 且第二个 * 替换为空字符串，或者将第一个 * 替换为空字符串且第二个 * 替换为 b。

给定 $S$，编写一个程序来回答以下查询：

• 给定一个字符串 $T$，确定 $T$ 和 $S$ 是否匹配，如果匹配，匹配是否唯一。

输入格式

输入的第一行包含一个由英文小写字母组成的字符串 $S$。($1 \le |S| \le 300\,000$)

输入的第二行包含一个整数 $Q$，表示查询的数量。($1 \le Q \le 300\,000$)

接下来的 $Q$ 行，每行包含一个字符串 $T_i$。$T_i$ 由英文小写字母和 * 组成。

所有查询中 $T_i$ 的长度之和不超过 $300\,000$。

输出格式

对于每个 $T_i$，如果它与 $S$ 不匹配，则输出 0；如果匹配唯一，则输出 1；否则输出 2。

样例

样例输入 1

axbbc
3
abc
a*c
a*b*c

样例输出 1

0
1
2