Angie really enjoys studying number theory, and because she enjoys studying it so much, she created her own number theoretic function - which she aptly named the Number Theoretic Transform. She begins with two odd primes $p$ and $q$ (let's call their product $N$). She then chooses another odd number $e$ and then computes $(p+q{)}^e$ and $(p-q{)}^e$ modulo $N$ (let's call these $c_1$ and $c_2$).

Lately, Angie has been having so much fun computing $c_1$ and $c_2$ that she lost track of her choice of $p$ and $q$ (which made her a bit sad). The first time this happened, she just picked new numbers and started again. However, after it kept happening throughout the day (a total of $T$ times), she got frustrated and would now like to recover her original choices of $p$ and $q$.

Given $T$ separate instances of $N$, $e$, $c_1$, and $c_2$, can you help her recover her choice of $p$ and $q$ in each instance?

Constraints

$1\le T\le 100$

$3\le p,q\le {10}^{18}$ (Notably, $p\cdot q=N\le {10}^{18}$ as well)

$1\le e\le {10}^{18}$

$0\le c_1,c_2<N$

$e$ is odd.

$p$ and $q$ are prime.

Input Specification

The first line of input contains a single integer, $T$.

Then, $T$ instances of the problem follow. Each line contains the integers $N$, $e$, $c_1$, and $c_2$ for that instance.

Output Specification

For each instance, output $p$ and $q$ in increasing order on its own line, separated by spaces.

Sample Input

1
1073 91 452 563

Sample Output

29 37