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
manjeet_: 2018-08-08 16:51:59

I made my own power function(binary exponentiation) and got TLE then I used c++ standar pow() and got accepted ... thanks to @Shashank Garg

mag1x_: 2018-06-14 19:07:47

https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence
Read Direct Definition and thank me later :)

ajayc1007: 2018-06-11 13:13:37

Apply recurrence relation
https://en.wikipedia.org/wiki/Thue-Morse_sequence

hunnychauhan: 2017-07-11 20:58:36

thue morse series
learned something new

Last edit: 2017-07-12 06:18:46
ashishranjan28: 2017-05-20 13:32:21

no recursion ... loop only :)

code96maker: 2017-04-02 20:25:07

accepted ...after 1 WA.

cake_is_a_lie: 2017-03-02 05:37:54

O(1); but an extra WA for initially using the wrong builtin.

lt: 2016-11-29 09:25:10

Simple recursion! :)
Python is not supported, had to submit python2.7 code into PyPy2.6...but worked fine.

poda_venna: 2016-08-30 18:51:38

Mapppppppps :p AC in one go :P

venture_walk: 2016-07-26 15:22:55

took me long enough


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 C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem