题目描述
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.
输入格式
见题面
输出格式
见题面