You are given an array A of size N. You would be asked Q queries.
In each query, you would be given two integers R,T. For each query find the number of R-tuples such that gcd of all the elements of that tuple is T. Since this number can be large, print its remainder when divided by 1000000007.
First line contains the integer N.
Second line contains the elements of the array A separated by a space.
Third line contains the integer Q.
Next Q lines contains two integers R and T separated by space.
For each query, print the desired result on separate line.