Cho một dãy số gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\). Với mỗi tập con khác rỗng \(S = (i_1, i_2, \ldots, i_k)\) \((0 < k \leq n, 1 \leq i_1 < i_2 < \ldots < i_k \leq n)\), gọi \(f(S)\) là số nguyên nhỏ nhất mà chia hết cho mọi \(a_{i_j}\) \((1 \leq j \leq k)\), tức là

Yêu cầu: Hãy tính \(R = \sum f(S)\) với tất cả mọi tập con \(S\) khác rỗng. Vì \(R\) có thể rất lớn nên chỉ cần đưa ra số dư của \(R\) khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(T\) \((1 \leq T \leq 10)\) là số bộ dữ liệu.
• \(T\) nhóm dòng sau, mỗi nhóm dòng thể hiện một bộ dữ liệu có dạng sau:
  • Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 100)\) --- là số phần tử của dãy.
  • Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 500)\).

Output

• Gồm \(T\) dòng, mỗi dòng là kết quả của các bộ dữ liệu theo đúng thứ tự trong đầu vào.

Scoring

• Subtask 1 (\(15\%\) số điểm): \(n \leq 20, a_i \leq 20\).
• Subtask 2 (\(20\%\) số điểm): \(n \leq 20\).
• Subtask 3 (\(25\%\) số điểm): Bội chung nhỏ nhất của \(n\) số nguyên dương không vượt quá \(50000\).
• Subtask 4 (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2
2 4
10
1 2 3 4 5 6 7 8 9 10
3
20 3 14

10
516031
699