Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Meena O Dosto Sele

Limits: 1s, 1.0 GB

Dosto sele Dipu and his friends used to disturb Rita Apu everyday on her way to school singing , “ রিতা ও রিতা, তুমি আমার মিতা “

This annoyed Meena very much and she wanted to teach Dipu and his friends a lesson. So, she decided to invite Dipu to play a game against her and beat Dipu every time they play the game.

At the start of the game, Meena choses a number N. Both the players play optimally. They take turns alternately and Meena moves first.

A move is adding a number 2K with current N to get the new N provided that

N >= 2(K+2)

N % 2(K+2) >= 2K

N % 2(K+2) < 2(K+1)

The player who can’t make a move loses the game.

Meena is having trouble deciding which number to choose to start the game with so that she can win every time . She needs your help. Given a number N , can you tell her if she can win starting the game with that number ?

Input

Input starts with an integer T denoting the number of test cases. Each of the following T lines will contain a number N denoting the number Meena wants to start the game with.

1 < = T <= 105

0 <= N <= 1018

Output

For each test case, output a single line containing “Meena” if Meena wins the game or “Dipu” if Dipu wins the game . See the sample below for better understanding.

Samples

InputOutput
3
6
9
10
Dipu
Dipu
Meena

Author
Discussion
Submit

Login to submit