Question
Count Numbers Divisible by A, B, or C in Range
You are given three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression. You are also given KaTeX can only parse string typed expression queries. Each query consists of two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
For each query, your task is to find how many integers in the range KaTeX can only parse string typed expression (inclusive) are divisible by at least one of KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, or KaTeX can only parse string typed expression.
Input
The first line contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression.
The second line contains a single integer KaTeX can only parse string typed expression — the number of queries.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
The second line contains a single integer KaTeX can only parse string typed expression — the number of queries.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Output
For each query, print a single integer — the count of numbers in the range KaTeX can only parse string typed expression that are divisible by at least one of KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, or KaTeX can only parse string typed expression.
Example
Input
2 3 5
3
1 10
10 20
1 100
Output
8
7
74
Explanation
For the query (1, 10): numbers divisible by 2, 3, or 5 are:
2, 3, 4, 5, 6, 8, 9, 10 → total = 8
For the query (10, 20):
10, 12, 14, 15, 16, 18, 20 → total = 7
For the query (1, 100):
Count all numbers divisible by 2, 3, or 5 in the range → total = 74
2 3 5
3
1 10
10 20
1 100
Output
8
7
74
Explanation
For the query (1, 10): numbers divisible by 2, 3, or 5 are:
2, 3, 4, 5, 6, 8, 9, 10 → total = 8
For the query (10, 20):
10, 12, 14, 15, 16, 18, 20 → total = 7
For the query (1, 100):
Count all numbers divisible by 2, 3, or 5 in the range → total = 74