Count Coprime Subsequences
60% Success432 Attempts30 Points5s Time Limit256MB Memory1024 KB Max Code

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\)
Examples
Input
5
4
1 1 1 1
5
2 4 6 8 10
6
1 2 3 4 5 6
7
1 2 4 6 8 10 12
8
1 2 2 2 2 2 2 1
Output
15
5
43
13
27
Explanation
  • In first test case, every non-empty subsequence is co-prime, thus \(2^4 - 1 = 15\) subsequences.
  • In second test case, only length 1 subsequences ie. 5 subsequences are co-prime, every other subsequence has common factor of \(2 \) between adjacent elements.
  • In fourth test case, coprime subsequences are all length 1 subsequences and \([1, 2], [1, 4], [1, 6], [1, 8], [1, 10], [1, 12]\), thus \(7 + 6 = 13\) subsequences.
  • In fifth test case, the number of co-prime subsequences are, \(8\) (1-length), then \([1, 2]\) 6 times, \([2, 1]\) 6 times and \([1,2,1]\) 6 times, and \([1, 1]\), thus \(8 + 6 + 6 + 6 + 1 = 27\) subsequences.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results