A sequence \(S\) of length \(N\) is called co-prime sequence if \(GCD(S[i], S[i + 1]) = 1\) for \(0 \le i < N - 1\), i.e. every adjacent element is co-prime, any sequence of length \(1\) is a co-prime sequence.

Given an Array \(arr\) of length \(N\), find the number of non-empty co-prime subsequences of this array, modulo \(10^9+7\).

Input Format:

• First line contains an integer \(T\) denoting the number of test cases.
• First line of each testcase contains an integer \(N\) denoting length of \(arr\).
• Next line contains \(N \) space-seperated integer, denoting the elements of \(arr\).

Output Format:

• For each testcase, In a single line, print the number of non-empty co-prime subsequence of the array, modulo \(10^9+7\).

Constraints:

• \(1 \le T \le 10\)
• \(1 \le N \le 10^5\)
• \(1 \le arr[i] \le 10^5\)