In a country named Ajob Desh, people play a game called Ajob Game (or strange game). This game is actually a game of words. The rules for the game are as follows:
- It's an N player game and players are numbered from 1 to N. And the players alternate turns in a circular way. Player 1 starts first. The next turn is for player 2, then player 3 and so on. After the turn for the Nth player, player 1 gets his/her turn again and the same procedure is continued.
- In each turn a player has to propose a pair of words. Each of the words should have length L, and the words should differ in exactly M positions. As their language has K alphabetical symbols, a word is a collection of symbols from these K alphabets.
- The pair of words proposed by a player should differ in exactly M positions, meaning there should be exactly M positions where the two words have different symbols, and in other positions they have the same symbols. For example, "abc" and "abd" differ in exactly 1 position, "abc" and "aca" differ in exactly 2 positions, "abc" and "cab" differ in exactly 3 positions.
- In each turn, a player has to propose a new pair of words. Two pairs are different if at least one word is different. Note that here pair refers to unordered pair. Let A, B, C be three different words, then (A, B) and (B, A) are the same, but (A, C) and (A, B) are different. For example, if a player already proposed {"abc", "def"}, then none can propose {"abc", "def"} or {"def", "abc"}. But a player can propose {"abc", "fed"} or {"abc", "abc"} or {"pqc", "abc"} etc.
- If a player fails to propose a new pair of words, he/she is treated as the loser of the game. And the game ends.
Let N = 2, K = 2, L = 2, M = 1 and the alphabet is {'a', 'b'}. All the words of length 2 are: {"aa", "ab", "ba", "bb"}. Player 1 chooses pair {"aa", "ab"} (differs in 1 position as M = 1) then player 2 chooses pair {"ab", "bb"}. After that player 1 chooses {"aa", "ba"} then player 2 chooses {"bb", "ba"}. And then there is no pair left for player 1, and so, player 1 will lose.
Now, this game is played by N players who know this game very well thus they play optimally. You are given N, K, L and M; you have to find the losing player.
Input
Input starts with an integer T (≤ 200), denoting the number of test cases.
Each case starts with a line containing four integers N (2 ≤ N ≤ 10000), K (1 ≤ K ≤ 109), L (1 ≤ L ≤ 105) and M (0 ≤ M ≤ L).
Output
For each case, print the case number and the player who loses the game.
Sample
Sample Input | Sample Output |
---|---|
5 2 2 2 1 3 4 3 3 9 26 8 5 10 2 2 2 100 3 2 0 | Case 1: 1 Case 2: 1 Case 3: 5 Case 4: 3 Case 5: 10 |