In a galaxy, far far away, there was a planet, Gringo quite similar to our own. Maybe it is because the planet has a similar "Sun" and "Moon". In Gringo, people use a calendar which is identical to ours. It is said this calendar was made by one of many kings in Gringo's history thousands of years ago. In the legend, it says the king liked programming very much, and at one night he solved a very difficult problem. He was so happy that he wanted to make a new calendar to congratulate. Hence in his calendar, this very midnight with full moon is first second.

In this calendar, names of periods of time are same to ours, like days, months, years, minutes and seconds. In Gringo planet, the planet will reach same position on its revolution around the "Sun" every T1 seconds, the time between two neighbor full moons is T2 seconds and the time between two neighbor midnights is T3 seconds. It's very clear that a year is T1 seconds and a day is T3 seconds. And luckily, T1 is divisible by T3. So a leap year is unnecessary.

But T2 may be not divisible by T3, which is very troublesome. But our king was very clever, he made following rules.

1. A new day comes when a midnight come.
2. A new year comes when the planet reaches the same position with the "first midnight" on its revolution around the "Sun". Of course it will be a midnight and a new day will come, too.
3. When a new day comes, if the "Moon" will be full in this day, a new month will come, too.
4. When a new year comes, a new month will come, too. The "Moon" may not be full. So the month was called "0th month" of a year, until a new full moon come.
5. Due to these complex rules, it is very difficult to calculate how many days in a month. Now many people in Gringo are turning to you for help.

Input

There are multiple test cases. The first line of input contains an integer T (T <= 20), indicating the number of test cases. Then T test cases follow. There is a blank line between different test cases. The first line of each test case contains 3 integers T1, T2 and T3 (1 <= T3 <= 10000, 5 <= T1 / T3 <= 1000, T1 is divisible by T3, T3 < T2 < T1). The next line contains an integer Q (1 <= Q <= 100). Then Q lines follow, each line contains two integer Yi and Mi, means the Mi^th month in Yi^th year, (1 <= Yi <= 5000, 0 <= Mi <= 5000).

Output

For each query, output how many days in that month. If there is no such month, output 0.

Sample

Input:
1
3650 295 10
4
1 1
1 2
2 0
2 13

Output:
29
30
18
0