Problem I

Coco Monkey

Time Limit

2 Seconds

This is the story of a time long ago. There were these sailors stranded on a beautiful island full off coconut trees. And what do our sailors do with the coconut trees? They collect all the coconuts and divide those among themselves and the monkeys that they brought with them!

History tells us that there were S sailors on the island, and they collected C coconuts in total. At nightfall they decided to leave the coconuts in a secret place and divide it equally in the morning. But as the night grew darker, the sailors began to get impatient. At midnight, one of the sailors got up. He dug up the coconuts and saw that after dividing the coconuts equally into S baskets, there are exactly M coconuts left. These, as you must have guessed, goes to the M monkeys that they have brought with them. Now, our greedy sailor took one of those baskets for himself and left the remaining S-1 ones for his commodores. History repeats. So we have another sailor succumbing to the temptation of juicy coconuts. He again, divided the remaining coconuts equally in S baskets only to find M coconuts extra. One basket for himself, M coconuts for the M monkeys and the remaining S-1 baskets for his fellows – that’s how it goes.

Before the night was over each and every sailor played his part exactly once. At dawn when they started to divide the remaining coconuts, they found that there’s no extra coconut left for the monkeys. But the monkeys would not complain, nor would any of the sailors. They had their share alright.

Historians, as one would expect, can be trusted for facts not for the figures. So whatever they would say about the values of S, C and M cannot be trusted entirely. But given the values of S, M and an interval for C one can identify possible values for C. As a programmer you only need to count the number of valid C values on a given range [low, high] inclusive.

Input
The first line of the input gives you the number of test cases, T (1 ≤ T ≤ 15). Then T test cases follow. Each of the test cases consists of four integers and is presented one in each line. The first integer gives you the number of sailors S (1 < S ≤ 100), then the next integer gives you the number of monkeys M (0 ≤ M < S). The next two integers will give you the value of low and high (0 ≤ low ≤ high ≤ 108).

Output
For each of the test cases, you need to print one line of output. The output for each test case starts with the test case number, followed by the number of valid C values in the range [low, high]. For the exact format of output, please consult the sample input/output section.

Sample Input

Output for Sample Input

3
3 2 49 50
4 2 5 10000
6 4 1 100000000

Case 1: 1
Case 2: 10
Case 3: 357

Illustration

The first test case gives you 3 sailors, 2 monkeys and a range of [49, 50] to choose from. If you’d try to do the math in hand, you’d see that only 50 would satisfy the scenario. So the answer for the first test case has to be 1. Here’s the brief illustration:

Sailor #

Total Coconuts

His share

Monkey’s share

Remaining Coconuts

1

50

16

2

32

2

32

10

2

20

3

20

6

2

12

Note of caution

If you’re thinking of a straightforward brute-force simulation, try the third test case. We cannot really let such a slow solution pass, can we?


Problem setter: Monirul Hasan
Member of Elite Problemsetters' Panel
Special thanks to Sadrul Habib Chowdhury & Mohammed Shamsul Alam