Andy 和 Andrew 是非常聪明的人，他们喜欢在空闲时间玩各种游戏。最令人惊奇的是，他们总能找到最佳策略，这也是他们感到反复无聊的原因。正如他们平时所做的那样，他们刚刚发明了一个新游戏。

游戏开始时，他们写下一个字符串 $S = s_1s_2s_3 \dots s_k$，然后轮流（Andy 先手）进行以下操作之一：

• 1. 擦除 $S$ 的最左侧字符，即 $S = s_2s_3s_4 \dots s_k$。
• 1. 擦除 $S$ 的最右侧字符，即 $S = s_1s_2s_3 \dots s_{k-1}$。

当 $S$ 为空或 $S \in A$（$A$ 是给定的字符串列表）时，下一位操作的玩家输掉游戏。

例如，设 $S = dzxx$ 且 $A = \{z, dz\}$。如果 Andy 擦除了 'x'，那么 Andrew 可以擦除另一个 'x'，因为此时 $S = dz$ 且 $dz \in A$，下一位玩家 Andy 输。否则，如果 Andy 擦除了 'd'，那么 Andrew 可以擦除 'z'，导致 Andy 处于失败状态。

给定一个字符串 $T = t_1t_2t_3 \dots t_n$ 和一个字符串列表 $A = \{a_1, a_2, \dots, a_m\}$。你的任务是找出如果 $S$ 是 $T$ 的某个子串，谁会获胜。Andy 和 Andrew 会玩很多次，因此你需要回答多个询问。

输入格式

第一行包含一个整数 $t$，表示测试用例的总数。接下来的行描述了每个测试用例。

每个测试用例的第一行包含三个整数 $n, m, q$，分别表示 $T$ 的长度、$A$ 的大小以及询问次数。 第二行包含一个字符串，表示 $T$。 接下来的 $m$ 行，每行包含一个字符串，表示 $a_i$。 接下来的 $q$ 行，每行包含两个整数 $l, r$，表示一个询问，你需要输出当 $S = t_lt_{l+1} \dots t_r$ 时谁会获胜。

数据范围

• $1 \le t \le 21$
• $1 \le n, q \le 40000$
• $1 \le m \le 10000$
• $1 \le \sum_{i=1}^{m} |a_i| \le 10000$
• $1 \le l \le r \le n$
• $T$ 和 $A$ 中的字符串仅由小写英文字母组成。
• 至多有 6 个测试用例满足 $n > 5000$。

输出格式

对于每个询问，如果 Andy 获胜，则在一行中输出 "1"（不含引号），否则输出 "0"（不含引号）。

样例

输入 1

1
10 4 10
zzzabcdzxx
a
z
dz
abcd
1 3
1 4
3 6
3 7
3 8
3 9
4 4
4 5
5 5
7 10

输出 1

0
1
1
1
0
1
0
1
1
0