H. X Y ?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After Getting fired again, Da7doo7 called FzArK who gave him a job as a mathematician. On his first day, FzArk gave him this problem and he forward it to you because Da7doo7 is bad at math.

You are given a tuple $$$\langle p, a, b, x, y \rangle$$$ of positive integers that satisfy the following:

  • $$$p$$$ is a prime number
  • $$$a$$$ and $$$b$$$ are relatively prime
  • $$$p \;\; \vert \;\; x^a - y^b$$$

You have to answer $$$Q$$$ queries. In each query, help $$$\texttt{F} z \texttt{ArK}$$$ find the $$$\textbf{smallest}$$$ positive integer $$$z$$$ such that: (in case it exists)

  • $$$p \;\; \vert \;\; z^a - y$$$
  • $$$p \;\; \vert \;\; z^b - x$$$
Note

Recall that for arbitrary positive integers $$$x$$$ and $$$y$$$, "$$$x \;\; \vert \;\; y$$$" $$$\textbf{is equivalent to}$$$ "$$$y$$$ is divisible by $$$x$$$".

Input

The first line contains a single integer $$$Q$$$ $$$(1 \le Q \le 10^5)$$$ denoting the number of queries.

The $$$i$$$-th of the next $$$Q$$$ lines contains five integers $$$p_i, a_i, b_i, x_i, y_i$$$ $$$(1 \le p_i, a_i, b_i, x_i, y_i \le 10^9 + 7)$$$.

It is guaranteed that $$$p_i$$$ is a prime number, $$$a_i$$$ and $$$b_i$$$ are relatively prime, and $$$p_i \;\; \vert \;\; x_i^{a_i} - y_i^{b_i}$$$.

Output

For each query, if no such $$$z$$$ exists, output $$$-1$$$. Otherwise, output the $$$\textbf{smallest}$$$ positive integer $$$z$$$ that satisfies both of the conditions.

Example
Input
3
2 2 1 4 6
7 10 3 13 2
67 3 2 1 1
Output
2
5
1