Consider a special family of Engineers and Doctors with following rules :
	Everybody has two children.
	First child of an Engineer is an Engineer and second child is a Doctor.
	First child of an Doctor is Doctor and second child is an Engineer.
	All generations of Doctors and Engineers start with Engineer.
We can represent the situation using below diagram:
                E
           /        \
          E          D
        /   \       /  \
       E     D     D    E
      / \   / \   / \   / \
     E   D D   E  D  E  E  D
Given level and position(pos) of a person in above ancestor tree, find profession of the person.
Example 1:
Input: level = 4, pos = 2
Output: Doctor
Explaination: It is shown in the tree given 
in question.
Example 2:
Input: level = 3, pos = 4
Output: Engineer
Explaination: Already given in the tree in 
question.
Your Task:
You do not need to read input or print anything. Your task is to complete the function profession() which takes level and pos as input parameters and returns 'd' if it is a doctor. Otherwise return 'e'. The driver code will output Doctor for 'd' and Engineer for 'e' itself.
Expected Time Complexity: O(log(pos))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ level ≤ 10^{9}
1 ≤ pos ≤ min(10^{9}, 2^{level-1})

Source: geeksforgeeks | Difficulty: EASY
Tags: Complete search

Starter code: #User function Template for python3



class Solution:

    def profession(self, level, pos):

        # code here

Solutions:
class Solution:

	def profession(self, level, pos):

		def recursion(level, pos):
			if pos == 1:
				return 'e'
			if recursion(level - 1, (pos + 1) // 2) == 'e':
				if pos % 2 == 0:
					return 'd'
				else:
					return 'e'
			elif pos % 2 == 1:
				return 'd'
			else:
				return 'e'
		ans = recursion(level, pos)
		return ans


class Solution:

	def profession(self, level, pos):
		curr = 0
		for x in range(level - 1):
			if not pos & 1:
				curr ^= 1
			pos = (pos - 1) // 2 + 1
			if pos == 1:
				break
		if curr == 0:
			return 'e'
		return 'd'


class Solution:

	def profession(self, level, pos):

		def countSetBits(n):
			count = 0
			while n > 0:
				n &= n - 1
				count += 1
			return count
		c = countSetBits(pos - 1)
		if c % 2 == 0:
			return 'e'
		else:
			return 'd'


class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		if self.profession(level - 1, (pos + 1) // 2) == 'd':
			if pos % 2:
				return 'd'
			else:
				return 'e'
		if pos % 2:
			return 'e'
		else:
			return 'd'


import sys
sys.setrecursionlimit(100 ** 3)

class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		if self.profession(level - 1, (pos + 1) // 2) == 'd':
			if pos % 2:
				return 'd'
			else:
				return 'e'
		if pos % 2:
			return 'e'
		else:
			return 'd'


class Solution:

	def profession(self, level, pos):
		return ['e', 'd'][bin(pos - 1).count('1') % 2]


class Solution:

	def profession(self, level, pos):
		if level == 1 or pos == 1:
			return 'e'
		if pos == 2:
			return 'd'
		if self.profession(level - 1, (pos + 1) // 2) == 'e':
			if pos % 2 == 0:
				return 'd'
			else:
				return 'e'
		elif pos % 2 == 0:
			return 'e'
		else:
			return 'd'


class Solution:

	def profession(self, level, pos):
		if level == 1 or pos == 1:
			return 'e'
		parent = (pos + 1) // 2
		char = self.profession(level - 1, parent)
		if pos == 2 * parent - 1:
			return char
		if char == 'e':
			return 'd'
		return 'e'


class Solution:

	def profession(self, level, pos):
		if pos == 1 or level == 1:
			return 'e'
		check = self.profession(level - 1, (pos + 1) // 2)
		if check == 'e' and pos % 2 != 0:
			return 'e'
		if check == 'd' and pos % 2 == 0:
			return 'e'
		else:
			return 'd'


class Solution:

	def profession(self, level, pos):
		if pos == 1 or level == 1:
			return 'e'
		prof = self.profession(level - 1, (pos + 1) // 2)
		if prof == 'e' and pos % 2 != 0:
			return 'e'
		if prof == 'd' and pos % 2 == 0:
			return 'e'
		return 'd'


class Solution:

	def profession(self, level, pos):
		ans = post(level, pos)
		return ans

def post(level, pos):
	if pos == 1:
		return 'e'
	parent = post(level - 1, (pos + 1) // 2)
	if pos % 2 == 1:
		return parent
	if parent == 'e':
		return 'd'
	return 'e'


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		par = self.profession(level - 1, (pos + 1) // 2)
		if pos % 2 != 0:
			return par
		if par == 'e':
			return 'd'
		else:
			return 'e'


class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		parent = self.profession(level - 1, (pos + 1) // 2)
		if pos % 2 != 0:
			return parent
		if parent == 'e':
			return 'd'
		return 'e'


class Solution:

	def profession(self, l, p):

		def solve(p):
			if p == 0:
				return 'e'
			x = solve(p // 2)
			if x == 'e':
				return 'e' if p % 2 == 0 else 'd'
			else:
				return 'd' if p % 2 == 0 else 'e'
		return solve(p - 1)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(level, pos) = [int(x) for x in input().split()]
		ob = Solution()
		if ob.profession(level, pos) == 'd':
			print('Doctor')
		else:
			print('Engineer')


class Solution:

	def profession(self, level, pos):
		if pos == 1 or level == 1:
			return 'e'
		parentProfession = self.profession(level - 1, (pos + 1) // 2)
		if pos % 2 != 0:
			return parentProfession
		elif parentProfession == 'e':
			return 'd'
		else:
			return 'e'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(level, pos) = [int(x) for x in input().split()]
		ob = Solution()
		if ob.profession(level, pos) == 'd':
			print('Doctor')
		else:
			print('Engineer')


class Solution:

	def countSetBits(self, n):
		count = 0
		while n > 0:
			n &= n - 1
			count += 1
		return count

	def profession(self, level, pos):
		c = self.countSetBits(pos - 1)
		if c % 2 == 0:
			return 'e'
		else:
			return 'd'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(level, pos) = [int(x) for x in input().split()]
		ob = Solution()
		if ob.profession(level, pos) == 'd':
			print('Doctor')
		else:
			print('Engineer')


from functools import lru_cache

class Solution:

	def profession(self, level, pos):

		@lru_cache(None)
		def solve(n, k):
			if k == 1:
				return 'e'
			ch = solve(n - 1, (k + 1) // 2)
			if k % 2 != 0:
				return ch
			elif ch == 'e':
				return 'd'
			else:
				return 'e'
		return solve(level, pos)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(level, pos) = [int(x) for x in input().split()]
		ob = Solution()
		if ob.profession(level, pos) == 'd':
			print('Doctor')
		else:
			print('Engineer')


class Solution:

	def profession(self, level, pos):
		if level == 1 or pos == 1:
			return 'e'
		parent = self.profession(level - 1, (pos + 1) // 2)
		if not pos % 2 == 0:
			return parent
		else:
			return 'e' if parent == 'd' else 'd'


from collections import deque

class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		c = self.profession(level - 1, (pos + 1) // 2)
		if pos % 2 != 0:
			return c
		elif c == 'e':
			return 'd'
		else:
			return 'e'


class Solution:

	def profession(self, level, pos):
		l = ['e', 'd']
		c = 0
		while pos > 2:
			p = 2
			while p * 2 < pos:
				p *= 2
			pos -= p
			c += 1
		if c % 2 != 0:
			l.reverse()
		return l[pos - 1]


class Solution:

	def profession(self, level, pos):
		if level == 1 or pos == 1:
			return 'e'
		parent = (pos + 1) // 2
		parentprof = self.profession(level - 1, parent)
		if pos == 2 * parent - 1:
			return parentprof
		elif parentprof == 'e':
			return 'd'
		else:
			return 'e'


class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		a = self.profession(level - 1, int((pos + 1) / 2))
		if a == 'e':
			if pos % 2 == 0:
				return 'd'
			else:
				return 'e'
		elif pos % 2 == 0:
			return 'e'
		else:
			return 'd'


class Solution:

	def profession(self, level, pos):

		def solve(level, pos):
			if level == 0:
				return 0
			mid = 2 ** (level - 1)
			if pos < mid:
				s = solve(level - 1, pos)
				return s
			s = solve(level - 1, pos - mid) ^ 1
			return s
		pos -= 1
		c = 0
		for i in range(32):
			if pos & 1 << i:
				c ^= 1
		s = ['e', 'd']
		return s[c]


class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		l = level - 1
		p = (pos + 1) // 2
		if self.profession(l, p) == 'e':
			if pos % 2 == 1:
				return 'e'
			else:
				return 'd'
		elif pos % 2 == 1:
			return 'd'
		else:
			return 'e'


class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		flips = 0
		while pos != 1:
			order = 1
			while pos > order:
				order *= 2
			pos = pos - order / 2
			flips += 1
		if flips % 2 == 0:
			return 'e'
		else:
			return 'd'


class Solution:

	def profession(self, level, pos):
		pos_copy = pos - 1
		ones_count = 0
		while pos_copy:
			if pos_copy % 2:
				ones_count += 1
			pos_copy >>= 1
		if ones_count % 2:
			return 'd'
		else:
			return 'e'


class Solution:

	def profession(self, level, pos):
		pos -= 1
		cnt = 0
		while pos:
			cnt += 1
			pos &= pos - 1
		return 'e' if cnt % 2 == 0 else 'd'


class Solution:

	def profession(self, level, pos):
		x = 0
		pos -= 1
		while pos:
			x += pos & 1
			pos //= 2
		if x & 1 == 0:
			return 'e'
		return 'd'


class Solution:

	def profession(self, level, pos):
		flip = False
		while pos != 1:
			if pos % 2 == 0:
				flip = not flip
			pos = (pos + 1) // 2
		return 'd' if flip else 'e'


class Solution:

	def profession(self, level, pos):
		if pos == 1:
			return 'e'
		pos_updated = int((pos + 1) / 2)
		currOutput = self.profession(level - 1, pos_updated)
		if pos & 1:
			return currOutput
		else:
			if currOutput == 'e':
				return 'd'
			return 'e'


class Solution:

	def profession(self, level, pos):
		count = 0
		N = pos - 1
		while N:
			N &= N - 1
			count += 1
		if count & 1:
			return 'd'
		else:
			return 'e'


class Solution:

	def profession(self, level, pos):
		if self.solve(pos):
			return 'e'
		else:
			return 'd'

	def solve(self, pos):
		if pos == 1:
			return True
		elif pos == 2:
			return False
		elif pos & 1:
			return self.solve(int((pos + 1) / 2))
		else:
			return not self.solve(int(pos / 2))


class Solution:

	def profession(self, level, pos):
		pos -= 1
		r = True
		while level - 1 and pos != 0:
			if pos % 2 == 1:
				r = not r
			pos //= 2
			level -= 1
		return 'd' if not r else 'e'