Mì ăn liền

Cho một đồ thị hai phía: nửa trái gồm $n$ đỉnh được đánh số từ $1$ đến $n$, nửa phải cũng gồm $n$ đỉnh được đánh số từ $1$ đến $n$. Mỗi đỉnh $i$ của nửa phải mang một số nguyên dương $c_i$.

Với một tập con $S$ khác rỗng các đỉnh của nửa trái, ký hiệu $N(S)$ là tập tất cả các đỉnh của nửa phải kề với ít nhất một đỉnh thuộc $S$, và $f(S)$ là tổng các số ghi trên những đỉnh thuộc $N(S)$.

Hãy tìm ước chung lớn nhất của $f(S)$ trên tất cả các tập con $S$ khác rỗng của nửa trái.

Nếu $N(S)$ rỗng thì $f(S)=0$; quy ước ước chung lớn nhất của tập rỗng bằng $0$, và $gcd(x,0)=x$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số lượng test.
• Mỗi test bắt đầu bằng dòng chứa hai số nguyên $n$ và $m$ là số đỉnh của mỗi nửa và số cạnh của đồ thị.
• Dòng tiếp theo chứa $n$ số nguyên $c_1,c_2,\dots ,c_n$ là các số ghi trên các đỉnh của nửa phải.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ mô tả một cạnh nối đỉnh $u_i$ của nửa trái với đỉnh $v_i$ của nửa phải.

Các test có thể được ngăn cách bởi dòng trống.

Dữ liệu ra

Với mỗi test, in ra trên một dòng ước chung lớn nhất cần tìm.

Ràng buộc

• $1\le t\le 500000$
• $1\le n,m\le 500000$
• $1\le c_i\le {10}^{12}$
• $1\le u_i,v_i\le n$
• Đồ thị không chứa cạnh lặp.
• Tổng $n$ trên tất cả các test không vượt quá $500000$, tổng $m$ trên tất cả các test cũng không vượt quá $500000$.

Ví dụ