Biswa and GCD

All submissions for this problem are available.
Biswa has an array A[ ] consisting of N integers.
He loves prime numbers, so he wants to calculate the value of the following function for his array:
F(A) = number of nonempty subsequences of A[ ] such that gcd of all numbers in that subsequence is a power of a prime number, i.e p^e for some prime p and e>=1.
Note: subsequences consisting of equal numbers occurring at different positions are considered different. (example: Array [2,2,2] has 7 nonempty subsequences)
However, Biswa's mischievous little brother Debu repeatedly makes some changes to the array. In each change, he selects an element of the array, and sets it to a new (or possibly same) value Y.
Help Biswa calculate F(A) after each change.
Input
The first line of Input consists of an integer T specifying the number of test cases. The description of T test cases follows:
The First line of each test case consists of two space separated integers, N and Q, the number of elements in Biswa's array, and number of changes performed by Debu on the array.
The next line contains N space separated integers A[1] , A[2] , ... , A[N]
Q lines follow, each line specifying a change, which is of the form:
X Y
denoting Xth element of array is set to the value Y.
Output
For each test case, output Q lines, each containing the value of F(A) modulo 1000000007 ( 10^9 + 7 )
Constraints
 1 ≤ T ≤ 3
 1 ≤ N ≤ 100000
 1 ≤ A[i] ≤ 1000000
 1 ≤ Q ≤ 100000
 1 ≤ X ≤ N
 1 ≤ Y ≤ 1000000
Example
Input: 2 3 2 2 4 8 1 2 1 5 1 1 2 1 1 Output: 7 4 0 Warning: Large Input data. Use faster input methods.
Author:  gvaibhav21 
Tags  gvaibhav21 
Date Added:  4022016 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions