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