Trong Bảy Viên Ngọc Rồng, hợp thể là cách hai đấu sĩ có thể cùng tạo nên một thực thể, mạnh hơn tổng sức mạnh của cả hai, nhằm mục đích dành chiến thắng trong một trận đấu. Một hợp thể có thể mạnh hơn tổng sức mạnh của hai đấu sĩ, nhưng cũng có thể yếu hơn, tùy vào độ xung-khắc giữa bộ sức mạnh của cả hai. Trong bài toán này, ta sẽ tìm hiểu cách tính sức mạnh hợp thể của hai đấu sĩ, biết chỉ số bộ sức mạnh của họ.

Mỗi đấu sĩ sẽ có một bộ gồm ~N~ chỉ số sức mạnh. Giả sử có đấu sĩ ~A~, với bộ chỉ số là ~A_1, A_2, \ldots, A_N~, và đấu sĩ ~B~, với bộ chỉ số là ~B_1, B_2, \ldots, B_N~, sức mạnh của hợp thể hai đấu sĩ sẽ là chỉ số ~K_{max}~ được tính như sau:

1. Xét tất cả các số nguyên dương ~M \ge 2~. Với mỗi ~M~, ta tìm ~K_M~, tương đương với đoạn chỉ số ~[l; r]~ (~1 \le l \le r \le N~) dài nhất thỏa mãn:

   • ~A_l \equiv B_l (\mod M)~

   • ~A_{l + 1} \equiv B_{l + 1} (\mod M)~

   • ~A_{l + 2} \equiv B_{l + 2} (\mod M)~

   • ~\ldots~

   • ~A_{r - 1} \equiv B_{r - 1} (\mod M)~

   • ~A_{r} \equiv B_{r} (\mod M)~

2. Từ đó, ta tính được ~K_{max}~ chính là giá trị ~K_M~ lớn nhất tìm được.

Cho bộ chỉ số sức mạnh của Piccôlô là ~P~, và bộ chỉ số sức mạnh của Goku là ~G~. Hãy tính sức mạnh ~K_{max}~ của hợp thể giữa Piccôlô và Goku. Bạn cũng phải in ra ~M~ lớn nhất tương ứng với ~K_{max}~ bạn tìm được.

Nếu không tính được ~K_{max}~ nào, chứng tỏ hai đấu sĩ không thể hợp thể với nhau: in ra -1.

Nếu ~M~ có thể lên tới vô hạn, chứng tỏ hai đấu sĩ phối hợp vô cùng ăn ý, ta in ra ~0~ cho giá trị của ~M~.

Input

Dòng đầu tiên chứa ~T~ (~1 \le T \le 100~) - số test trong một tệp đầu vào. Mỗi test sẽ có định dạng như sau:

• Dòng đầu tiên chứa ~N~ (~1 \le N \le 10^5~) - số phần tử ở cả hai dãy.

• Dòng thứ hai chứa ~P_1, P_2, \ldots, P_N~ (~1 \le P_i \le 10^9~), bộ chỉ số sức mạnh của Piccôlô.

• Dòng thứ ba chứa ~G_1, G_2, \ldots, G_N~ (~1 \le G_i \le 10^9~), bộ chỉ số sức mạnh của Goku.

Dữ liệu đảm bảo tổng của ~N~ trong tất cả các test sẽ không vượt quá ~5 * 10^5~.

Output

Với mỗi bộ test:

• In ra -1 nếu không tìm được ~M~ nào thỏa mãn.

• Ngược lại, in ra hai số ~K_{max}~ và ~M~ theo thứ tự, trên cùng một dòng, và cách nhau bởi một dấu cách. Hai số này tương ứng với độ dài dãy con lớn nhất bạn tìm được, và ước chung lớn nhất của nó.

• Nếu ~M~ tiến đến vô cùng, ta in ra ~0~ cho giá trị của ~M~.

Sample Input 1

4
8
8 14 5 17 23 6 10 13
6 10 11 8 26 18 18 9
9
8 14 5 17 23 6 10 13 1
6 10 11 8 26 18 18 9 21
3
1 3 5
2 4 6
5
3 4 6 7 2
3 4 6 7 2

Sample Output 1

4 3
4 4
-1
5 0

Notes

Ở bộ test ví dụ đầu tiên: dãy dài nhất tìm được là ~[2; 5]~ (~0~-indexed):

• ~5 \equiv 11 (\mod 3)~

• ~17 \equiv 8 (\mod 3)~

• ~23 \equiv 26 (\mod 3)~

• ~6 \equiv 18 (\mod 3)~

Ở bộ test ví dụ thứ hai, mặc dù nếu ta chọn ~M = 2~ hay ~M = 3~, cũng thỏa mãn tìm được ~K_M~ lớn nhất. Tuy vậy, ta phải in ra ~M = 4~ vì đề bài yêu cầu ~M~ lớn nhất có thể.

Ở bộ test ví dụ thứ ba, ta không tìm được bất kỳ ~M > 1~ nào mà thỏa mãn tồn tại ~i~ sao cho ~A_i \equiv B_i (\mod M)~.