作为一个冷血、热血且铁血的吸血鬼，忍（Shinobu）热爱四处旅行。

总共有 $P$ 个国家，编号为 $0, 1, \dots, P - 1$。（保证 $P$ 是一个质数）

已知当忍在编号为 $i$ 的国家时，她下一个访问的国家必须是编号为 $(i \cdot a) \pmod P$ 的国家（$a$ 是一个常数参数），且从一个国家前往另一个国家需要花费 1 天时间。

为了旅行顺利，忍定制了 $n$ 个旅行计划，第 $i$ 个旅行计划由起始国家 $s_i$ 和旅行天数 $d_i$ 表示。

例如，如果 $P = 233$，$a = 2$，某个计划的起始国家为 $1$，旅行天数为 $2$，那么忍将根据该计划访问城市 $\{1, 2, 4\}$。

Playf 知道这些旅行计划以及参数 $a$ 的值，现在他想问你 $q$ 个问题。第 $i$ 个问题询问有多少个不同的旅行计划会使忍访问国家 $x_i$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含四个整数 $P, a, n, q$ ($2 \le a < P \le 1000000007, 1 \le n \le 1000, 1 \le q \le 1000$)，分别表示国家数量、参数 $a$ 的值、忍的旅行计划数量以及 Playf 的询问数量。

接下来的 $n$ 行，每行包含两个整数 $s_i, d_i$ ($0 \le s_i < P, 1 \le d_i \le 200000$)，表示起始国家和旅行天数。

接下来的 $q$ 行，每行包含一个整数 $x_i$ ($0 \le x_i < P$)，表示 Playf 的询问。

保证 $P$ 是一个质数。

输出格式

对于每个测试用例，输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 个问题的答案。

样例

输入 1

2
3 2 1 1
1 1
2
5 4 3 2
1 4
4 3
2 100000
4
2

输出 1

1
2
1