Relief Supplies

Because of a snowstorm, you and your family are cold, hungry, and miserable. Worse still, the power is out and you cannot drive anywhere. Luckily, a nearby relief shelter hands out supplies such as food and blankets several times a day. You have noticed that the supplies are handed out in a very particular pattern, and you want to use this to obtain the items your family needs most.

A line of $N$ people forms to receive supplies. The shelter stocks $T$ different types of supplies and exactly $B$ boxes of each type. The first person in line receives a box of type 1, the second person receives a box of type 2, and so on. After a box of the last type (type $T$) is handed out, the type wraps around to type 1 again. Whenever the line reaches its end, distribution continues from the first person again, while the type keeps advancing from wherever it left off. Both the person and the type advance by one with every box handed out. This continues until no boxes remain (there are $T \times B$ boxes in total).

You know the single supply type $S$ that your family needs most. You want to decide where to stand in line so that you receive the second-most boxes of type $S$ — always receiving the most would look suspicious. However, if several positions tie for the most boxes of type $S$, then you are fine with receiving the most, and among those tied positions you prefer the one closest to the end of the line (the largest position number), since it is easier to reach. The same tie-breaking rule applies when several positions tie for the second-most.

The first line contains the number of data sets $K$. Each of the next $K$ lines contains four integers $N$, $T$, $B$, and $S$. Every integer is between 1 and 100 inclusive. In addition, $N \ge 2$ and $S \le T$.

For each data set, print a line “Data Set x:”, where $x$ is the data set number (starting from 1). On the next line, print the position in line where you should stand. Print a blank line between consecutive data sets.