steave-at-shop

Steave has abundant N types of coins.He went to a shop where price of each product was unique.Luckily the shopkeeper was his friend.He tells Steave that they are selling products in some price range [P,Q] everyday. 
He also tells Steave that for every price, there is a product in the shop but policy was that Customer may only use a single type of coin for each product which he purchases. 
For example, he could pay for a product of price 6 with two 3-coins, but not with a 2-coin and a 4-coin.
So you need to tell how many different types of products he can buy.

Input Format:

The first line of input contains N, the number of types of coins Steave has. 
Then the next N lines contain an integer each: the ith line contains A[i], the value of Steave's ith type of coin.

Then the next line contains a number T,number of test cases. 
Then each of the next T lines contains numbers P and Q, denoting that they are selling items in price range [P,Q].

Output format: 

There will be T lines, each containing the number of distinct items that can be bought in that particular range.

Constraints:

1 ≤N ≤ 20
1 ≤ A[i]≤ 60 
1 ≤ T ≤101 
1 ≤ P ≤ Q ≤ 10^18

SAMPLE INPUT
4
2
3
4
5
3
1 10
2 20
3 7

SAMPLE OUTPUT
8
14
4

Explanation

For Case 1: He can buy items of price {2,3,4,5,6,8,9,10},so total number of products are 8. 
For Case 2: He can buy items of price {2,3,4,5,6,8,9,10,12,14,15,16,18,20} so total 14 products.
For Case 3: He can buy items of price {3,4,5,6},so total 4 products.

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: