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
Ajinkya: 2012-07-25 09:46:14

whats the o/p for
9999 9999 ........????

npsabari: 2012-07-15 17:35:47

Awesome problem! :)
No need of 3s..

Last edit: 2012-07-15 17:38:31
Aradhya: 2012-07-01 13:02:20

nice problem :)

jaans: 2012-06-18 12:12:29

omg!!!!!!!! so silly mistake caused me sooooo many wrong answers :D :Dwrrrrrrrrrrrrrrrrrrrrrrrr!!!!!!!

Rajat Gupta: 2012-06-07 12:47:24

@dce_coder: Could you pls tell me where am i getting wrong or provide some hint.
submission id:7105882

Last edit: 2012-06-07 12:47:53
Deepak: 2012-06-04 14:32:54

Submission #7089552
Please can u check my solution i checked d test cases and a couple of my own still getting wrong answer....

PubLic_AvenGeR: 2012-05-31 06:56:18

Nice one :)

jaans: 2012-05-14 18:13:28

@dce_coders:please tell me why i am getting runtime error.. although i hve checked it for many values :)
<edit>
Got Ac :)

Last edit: 2012-06-18 12:37:14
Andres R. Arrieche S. [UCLA-ve]: 2012-05-01 17:22:07

@dce_coders Could you tell me which case my solution(6931842) fail or give me any hint?
Thanks in advance.

reply - your code gives wrong answer to most of the cases. you can easily check that for small values of n and k i believe :)

reply - I don't know why it doesn't work in java, I just rewrote it from java to C++ and got AC so my approach is ok.

Last edit: 2012-05-05 21:48:45

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