Game

Time limit0.1sMemory limit1024 MB

Summary

For each pair of positive integers A and B, decide who wins a subtraction game where a player may subtract any positive multiple of the smaller number from the larger, or take the remainder modulo the smaller.

Level: Medium7 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

Mirek likes playing with numbers. He plays the following game with his friend Kamil.

A game starts with two non-negative integers $A$ and $B$ . Assume $A \le B$ . The players take turns, and on a turn a player makes one of these two moves.

Replace $B$ with $B-AK$ . The player can pick any integer $K$ with $K>0$ and $B-AK \ge 0$ .
Replace $B$ with $B \bmod A$ .

If $B \le A$ , the same moves are available with the roles of the two numbers swapped. The player who turns either number into $0$ wins. Mirek always moves first.

Both players play optimally. For each game, determine whether Mirek or Kamil wins.

Input

The first line contains the number of games $T$ ( $1 \le T \le 10^4$ ). Each of the next $T$ lines describes one game and contains two integers $A$ and $B$ ( $1 \le A, B \le 10^{18}$ ).

Output

Print $T$ lines. Line $i$ contains the name of the winner of the $i$ -th game, either Mirek or Kamil.

Examples2

Example 1

Input

Expected output

Mirek
Mirek
Kamil
Mirek

Example 2
Input
```
1
2 3
```
Expected output
```
Kamil
```