一个序列 $(a_1, a_2, \dots, a_n)$ 被称为 $(n, m, d)$-好的，如果满足 $1 \le a_i \le m$ ($1 \le i \le n$) 且 $\gcd(a_1, a_2, \dots, a_n) = d$。

给定四个整数 $n, m, d$ 和 $k$，请计算所有 $(n, m, d)$-好的序列 $q$ 的 $f(q, k)$ 之和，其中对于序列 $q = (a_1, a_2, \dots, a_n)$，有 $f((a_1, a_2, \dots, a_n), k) = (a_1 a_2 \dots a_n)^k$。

由于答案可能非常大，你只需要输出答案对 $59964251$ 取模的结果。

输入格式

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

对于每个测试用例，第一行包含四个整数 $n$ ($1 \le n \le 10^{100000}$)，$m$ ($1 \le m \le 100000$)，$d$ ($1 \le d \le 100000$)，$k$ ($1 \le k \le 10^9$)，其含义如题目描述所述。

输出格式

对于每个测试用例，输出一行，包含一个整数。

样例

样例输入 1

1
3 3 3 1

样例输出 1

27