ACT 1: Ash Counting Trees

Ash Ketchum has a weird rooted tree (read Notes sections if you don't know about tree data structure). The tree has an infinite number of nodes (vertices). Each node has exactly $K$ child nodes. Ash named such trees $K$-child trees. That means, if $K = 2$, it is called a 2-child tree and the tree is an infinite binary tree. Similarly, a 3-child tree is an infinite ternary tree and so on. Initially, all the nodes in the tree are empty.

Ash wants to label exactly $N$ nodes of such a tree with some positive integers, abiding by the following rules:

1. A tree node $U$ can be labeled if either $U$ is the root node or the parent node of $U$ is already labeled.
2. A node can be labeled with the value $V$ only if the last labeled node was given value $V - 1$. If no node was labeled before, $V = 1$ should be used.
3. A node can not be labeled more than once.

Being a mathematical genius (thanks to his Abra Kadabra Alakazam), Ash designed a function $F(N, K)$ such that:
$F(N, K)$ = the number of different $K$-child trees Ash can obtain after labeling $N$ nodes following the rules stated above.

For example, $F(3, 2) = 6$ and the six trees Ash can obtain are shown in the following image:

He divides $F(N, K)$ by $P^Z$ such that $Z$ is maximum and $F(N, K)$ is divisible by $P^Z$. And then he finally finds

Your task is to help Ash find that.

In other words, given $N$, $K$, $P$ and $Q$, you have to find $\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$

Input

Input will start with an integer $T$ in a single line, denoting the number of test cases. The following $T$ lines will represent the test cases.

In each test case, four space-separated integers $N$, $K$, $P$ and $Q$ will be given in a single line.

Constraints

$1 \leq T \leq 100$
$1 \leq P \leq 10^6$
It is guaranteed that $P$ is a prime number in all subtasks.

Subtask 1 (5 points)

$1 \leq N, K \leq 10^{6}$
$Q = 1$

Subtask 2 (15 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 2$
$Q = 1$

Subtask 3 (35 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$Q = 1$

Subtask 4 (45 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$1 \leq P^Q \leq 10^6$
$Q \geq 1$

Output

For each testcase, print $\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$ in a single line.

Sample

Input	Output
7 2 2 5 1 3 2 7 1 3 2 5 1 3 2 2 1 3 2 3 1 3 3 17 1 15 5 7 1	2 6 1 1 2 15 3

Sample Explanation

First test case:

$F(2, 2) = 2$, so $Z = 0$ is the largest $Z$ such that $5^Z$ divides $F(2, 2)$.

Thus, $\displaystyle \frac{F(2, 2)}{5^0} = 2$ and answer is 2.

Second test case:

$F(3, 2) = 6$, so $Z = 0$ is the largest $Z$ such that $7^Z$ divides $F(3, 2)$.

Thus, $\displaystyle \frac{F(3, 2)}{7^0} = 6$ and answer is 6.

Third test case:

$F(3, 2) = 6$, so $Z = 0$ is the largest $Z$ such that $5^Z$ divides $F(3, 2)$.

Thus, $\displaystyle \frac{F(3, 2)}{5^0} = 6$. Here, $P^Q = 5^1 = 5$.

$\displaystyle \frac{F(3, 2)}{5^0} \equiv 1 \pmod {5^1}$, so answer is 1.

Fourth test case:

$F(3, 2) = 6$, so $Z = 1$ is the largest $Z$ such that $2^Z$ divides $F(3, 2)$.

Thus, $\displaystyle \frac{F(3, 2)}{2^1} = 3$. Here, $P^Q = 2^1 = 2$.

$\displaystyle \frac{F(3, 2)}{2^1} \equiv 1 \pmod {2^1}$, so answer is 1.

Notes

In computer science, a tree is a widely used abstract data type. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.