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