CAL - Strange Calendar

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 Mith month in Yith 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

Added by:paradigm2k10
Date:2010-08-20
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Fictious

hide comments
2011-10-26 21:31:45 Sandesh
I have submitted 3 different solutions, all giving different answers for many test case, surprisingly all of those are accepted :D
2011-06-23 09:52:45 mohak gupta
@paradigm2k10 - could you be more specific about the output format. The one you have shown seems to leave a blank line after each answer. what would be the output format in case of multiple test cases ??
2010-09-01 14:22:47 numerix
Why those language restrictions? Please open it for other/more/all languages.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.