Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3350
Strange Calender

Time Limit: 2 Seconds      Memory Limit: 32768 KB

In the Bzu planet people use a calendar which is similar to ours. Maybe it is because Bzu planet has a similar "Sun" and "Moon". It is said this calendar was made by one of many kings in Bzu's history in 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 Bzu 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.

Due to these complex rules, it is very difficult to calculate how many days in a month. Now many people in Bzu 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 Mith month in Yith year, (1 <= Yi <=5000, 0<= Mi <= 5000).

Output

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

Sample Input

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

Sample Output

29
30
18
0

Author: HUANG, Minzhi
Contest: ZOJ Monthly, June 2010
Submit    Status