## Gcd Again

Time Limit: 2 sec
Memory Limit: 256 MB
Attempts: 2
Accuracy: 50.00%
Author: ankit28

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.

Input Format:

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.

Output Format:

For each query, print the desired result on separate line.

Constraints:

1<=N<=50000

1<=Q<=50

1<=A[i]<=50000

1<=T<=50000

1<=R<=10^9

Sample Input:

4

1 2 3 4

3

1 1

2 1

3 1

Sample Output:

1

11

55

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED