Cho dãy số nguyên dương \(a_1, a_2, \dots, a_n\). Tìm số nguyên dương \(x\) nhỏ nhất thỏa mãn hai điều kiện:

• \(x\) là số chính phương.
• \(x\) chia hết cho tất cả các số \(a_1, a_2, \dots, a_n\).

Vì giá trị của \(x\) có thể rất lớn, bạn chỉ cần đưa ra số dư trong phép chia \(x\) cho \(10^9 + 7\).

Input

• Dòng 1 chứa số nguyên dương \(T \le 10\) là số test.
• \(T\) nhóm dòng tiếp theo, mỗi nhóm gồm 2 dòng chứa dữ liệu một test:
  • Dòng 1 chứa số nguyên dương \(n \le 10^5\).
  • Dòng 2 chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(\forall i: a_i \le 10^6\)).

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên duy nhất là số dư trong phép chia số \(x\) tìm được cho \(10^9 + 7\).

Example

2
3
1 2 3
6
1 2 3 4 5 6

36
900