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:

1. 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 N^th player, player 1 gets his/her turn again and the same procedure is continued.
2. 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.
3. 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.
4. 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.
5. 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 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 ≤ 10⁹), L (1 ≤ L ≤ 10⁵) and M (0 ≤ M ≤ L).

For each case, print the case number and the player who loses the game.