DCEPC504 - The Indian Connection

no tags 

Rajesh Kuthrapali has a weird family structure. Every male member gives birth to a male child first and then a female child whereas every female member gives birth to a female child first and then to a male child. Rajesh analyses this pattern and wants to know what will be the Kth child in his Nth generation. Help him.

Note:

  1. Every member has exactly 2 children.
  2. The generation starts with a male member (Rajesh).
  3. In the figure given below:
                               M ------------ 1st generation
                             /   \
                            /     \
                           /       \
                          M         F ------- 2nd generation
                        /   \     /   \
                       M     F   F     M
                                 |
                                3rd child of 3rd generation

Input

First line specifies T, the number of test cases.

Next T lines each gives 2 numbers, N and K.

Output

Output 1 line for each test case giving the gender of the Kth child in in Nth generation.

Print “Male” for male “Female” for female (quotes only for clarification).

Constraints

1 <= T <=100
1 <= N <=10000
1 <= K <= min(10^15, 2^(n-1))

Example

Input:
4
1 1
2 1
2 2
4 5

Output:
Male
Male
Female
Female

hide comments
Aditya Joshi: 2014-09-24 08:38:25

This is weird. Got a stackoverflow error in Java, but a Python solution got accepted.

Prajval Prabhakar: 2014-07-22 10:15:09

nice question

Last edit: 2014-08-08 23:45:35
Saket Malik: 2014-06-16 22:08:40

Last edit: 2014-06-19 20:00:34
code_do: 2014-06-13 23:39:55

getting WA :( Please someone help.. my code is http://ideone.com/18vSLY

Last edit: 2014-06-13 23:40:23
Ayush Vatsa: 2014-05-23 13:02:35

nice problem

GOKU: 2014-03-15 15:14:44

Why wrong answer...!!
Please specify any tricky test case??

Last edit: 2014-03-15 15:15:06
Mostafa 36a2: 2014-02-13 22:33:52

COLONY

Rohan Phadke: 2014-01-23 14:38:32

@dcecoders : i checked many testcases.. getting correct answers.. still getting WA :(.. could you please check my solution? ID 10923347 thanx in advance..

Abhinav Gupta: 2014-01-17 23:50:15

Nice problem...:)...Logical!!

do_do: 2014-01-14 09:11:05

getting WA :( my code gives correct output on terminal for all test cases... someone plzz help


Added by:dce coders
Date:2012-04-18
Time limit:1.726s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem