Given a sequence of integers $$$a_1, a_2, \dots, a_n $$$ where $$$( 1 \leq a_i \leq 10^6 )$$$, count the number of subsequences with indices $$$( i_1, i_2, \dots, i_k $$$)$ such that:

\begin{itemize} $$$ \item ( k > 0 ) $$$ $$$\item ( 1 < i_2 < \dots < i_k \leq n ),$$$ $$$\item ( a_{i_1} \leq a_{i_2} \leq \dots \leq a_{i_k} )$$$, $$$\item ( \gcd(a_{i_1}, a_{i_2}, \dots, a_{i_k}) = 1 ).$$$ \end{itemize}

\textbf{Input:}

The first line contains ( T ) ((1 \leq T \leq 3)), the number of test cases.

For each test case: \begin{itemize} \item The first line contains an integer ( n ) ((1 \leq n \leq 3 \times 10^5)), representing the number of elements in the sequence. \item The second line contains ( n ) integers ( a_1, a_2, \dots, a_n ) ((1 \leq a_i \leq 10^6)). \end{itemize}

\textbf{Output:}

Output ( T ) lines, where line ( i ) ((1 \leq i \leq T)) contains a single integer, which is the result for test case ( i ), modulo ( 10^9 + 7 ).