Cho một dãy số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^6)\). Hãy đếm số dãy con \(i_1, i_2, \ldots, i_k\) của dãy sao cho

• \(k > 0\),
• \(1 < i_1 < i_2 < \ldots < i_k \leq n\),
• \(a_{i_1} \leq a_{i_2} \leq \ldots \leq a_{i_k}\),
• \(\gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) = 1\).

Input

Dòng đầu tiên chứa \(T\) \((1 \leq T \leq 3)\) là số bộ dữ liệu.

\(T\) nhóm dòng sau, mỗi nhóm dòng có dạng như sau:

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 3 \times 10^5)\) là số phần tử của dãy.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^6)\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) \((1 \leq i \leq T)\) chứa duy nhất một số nguyên là kết quả của bộ dữ liệu thứ \(i\), trong modulo \((10^9 + 7)\).

Scoring

• Subtask 1 (\(10\%\)): \(n \leq 100, a_i \leq 100\).
• Subtask 2 (\(20\%\)): \(n \leq 3000\).
• Subtask 3 (\(30\%\)): Nếu \(i < j\) và \(a_i \leq a_j\) thì \(\gcd(a_i, a_j) = 1\).
• Subtask 4 (\(40\%\)): Không có ràng buộc gì thêm.

Example

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

1
5
3