Cho một dãy gồm \(n\) số nguyên dương \(a_{1},a_{2},...,a_{n}.\) Ước chung lớn nhất của dãy số nguyên \(a_{1},a_{2},...,a_{n}\) là số nguyên dương \(d\) thỏa mãn:

1. \(d\) là ước của tất cả các số \(a_{1},a_{2},...,a_{n},\)

2. \(d\) là số lớn nhất trong tất cả các ước của \(a_{1},a_{2},...,a_{n}.\)

Ví dụ như 20, 8, 12 có các ước chung là 1, 2, 4 nên 4 là ước chung lớn nhất của 20, 8, 12.

Xét một phép biến đổi dãy số nguyên \(a_{1},a_{2},...,a_{n}\) như sau:

Chọn hai số bất kì trong dãy (gọi là hai số \(A\) và \(B\)) và một số nguyên tố \(p\) sao cho \(A\) chia hết cho \(p\). Sau đó xóa số \(A\) đi và thay vào đó là số \(\frac{A}{p}\), xóa số \(B\) đi và thay vào đó là số \(B.p.\)

Bạn được phép thực hiện phép biến đổi đã cho với số lần tùy ý để biến đổi dãy \(a_{1},a_{2},...,a_{n}\) thành dãy mới \(b_{1},b_{2},...,b_{n}.\)

Yều cầu: Hãy lập trình tính giá trị lớn nhất (gọi là \(d\)) có thể của ước chung lớn nhất của dãy \(b_{1},b_{2},...,b_{n}\) qua một số phép biến đổi dãy và số phép biến đổi dãy ít nhất (gọi là \(c\)) để nhận được giá trị lớn nhất đó.

Dữ liệu vào:

+ Dòng đầu ghi số nguyên dương \(n\ (1 \leq n \leq 100);\)

+ Dòng thứ hai ghi \(n\) số nguyên \(a_{1},a_{2},...,a_{n}\left( 1 \leq a_{i} \leq 1000000,i = 1,2,...,n \right).\) Các số trên cùng một dòng cách nhau bởi một dấu cách.

Kết quả:

+ Ghi giá trị lớn nhất \(d\) có thể và số phép biến đổi ít nhất c để nhận được giá trị \(d\), hai số cách nhau bởi một dấu cách.

Ví dụ:

Giải thích:

• Test 1: Thực hiện một phép biến đổi dãy như sau: chọn \(A = 72,B = 8,p = 3\), thay số \(A = 72\) bằng số \(\frac{A}{p} = \frac{72}{3} = 24,\) thay số \(B = 8\) bằng số \(B.p = 8.3 = 24\). Dãy số đã cho biến đổi thành dãy mới \(24,24\) có ước chung lớn nhất là 24.

Hoặc có thể chọn \(A = 8,B = 72,p = 2\), thì dãy đã cho được biến đổi thành dãy \(4,144\) có ước chung lớn nhất là 4.

Có thể biến đổi \(8,72\) thành nhiều dãy mới. Tuy nhiên, trong trường hợp này cách biến đổi đầu tiên là cách thu được dãy mới có ước chung lớn nhất có thể là 24 qua một phép biến đổi dãy. Vì vậy, kết quả là \(241\).

• Test 2: Chọn \(A = 4,B = 5,p = 2\) thì dãy đã cho được biến đổi thành dãy \(2,10,6,7,8.\) Ta lại chọn tiếp \(A = 8,B = 7,p = 2\) thì dãy \(2,10,6,7,8\) được biến đổi thành dãy \(2,10,6,14,4\) Dãy mới \(2,10,6,14,4\) có ước chung lớn nhất là 2. Vì vậy, kết quả là \(22\).

Ràng buộc:

+ Có \(\frac{1}{2}\) số test của bài thỏa mãn: \(n = 2;\)

+ Có \(\frac{1}{2}\) số test còn lại của bài thỏa mãn: \(2 < n \leq 100.\)