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

By Shahin · 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 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


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.


Input Output



28% Solution Ratio

NirjhorEarliest, Aug '17

sahedsohelFastest, 32549.9s

NirjhorLightest, 655 kB

nazmulashaShortest, 514B


Login to submit

Related Contests

Battle of Brains, 2017 Ended at 2017-08-12 08:10:00 +0000 UTC
Replay of Battle of Brains, 2017 Ended at 2017-08-14 19:00:00 +0000 UTC
Nepal Team Selection Contest 2 for ACM-ICPC Dhaka Regional 2017 Ended at 2017-10-05 18:15:00 +0000 UTC