DCEPC504 - The Indian Connection

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

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

hide comments
2015-07-10 03:30:42 SangKuan
you can ignore the n
2015-06-26 11:35:39 Aditya Kumar
phew!! simple code with a silly mistake costed me WA's.
2015-06-23 18:25:13 Shashank Garg
same logic...used bitwise costed me 5 WAs.. used pow() and got AC
2015-04-25 20:23:28 Ankit Sultana
Beware of bitwise operators, if you are using one.
2015-04-14 11:49:46 Madhav
recursion works!!
2014-12-26 10:14:36 Deeksha
AC in 1st go :)
My 50th..

Last edit: 2014-12-26 10:15:48
2014-12-02 04:10:39 Hafeezul Rahman


Last edit: 2014-12-02 04:11:24
2014-11-18 17:52:08 Shubham Mohanka
my code worked without using 'n' at all.i wonder why it is given o.O
2014-11-13 21:55:22 .::Austin::.
AC in 0.0, silly overflow caused several WAs :(
2014-10-12 08:38:46 Shankar Chaudhary
finally accepted in 0.02s . small silly mistake cause 1 wa ,i used M & F instead of Male & Female :-p

Last edit: 2014-10-12 08:56:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.