number-game-6

Ketan and Dhruv are playing a very interesting game. They have 2 boxes - red and black. The red box contains all the natural numbers in increasing order(1,2,3,.....) and the black box contains all the natural numbers except "1" and each number is two times in the box in non-decreasing order(2,2,3,3,4,4,....).

The game is as follows :
In his chance the player takes out 1 number from red box and two numbers from black box and multiplies them. The result is added to the previous sum. If this is the 1st chance the previous sum is 0. Each player plays alternatively and Dhruv always starts the game. The person to make last move wins. If first chance is not possible game ends in a draw.

Note: You can only take out the numbers from top of the boxes.

You are given a number n, you need to find the number of chances such that achieved sum is strictly less than or equal to n. After that you need to tell the person who wins the game.

Input Format:-

First line contains t - number of test cases.

Next t lines contain a single integer n.

Output Format:-

Total 2*t lines, the first line of each test case contains the number of chances the game lasts for c and the next line contains the winner of the game.

If the winner is Ketan print "Ketan", if Dhruv print "Dhruv" and id the game is Drawn print "Draw", all without quotes.

Constrains:-

1 ≤ t ≤ 10^5

1 ≤ n ≤ 10^17

Author :- Nikhil Tekwani

SAMPLE INPUT
2
3
7

SAMPLE OUTPUT
0
Draw
1
Dhruv

Explanation

For the first test case, if Dhruv makes a move the sum becomes 1x2x2 = 4, which is greater than 3, thus no 1 is able to make a move and the game ends in a draw.

For the second test case, if Dhruv makes a move the sum becomes 1x2x2 = 4, and if Ketan makes a move the sum becomes 4 + 2x3x3 = 22. Since 4<7<22. Dhruv wins ans total chances is 1.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from bisect import bisect_left, bisect

result = [(n*(n+1)*(n+2)*(3*n+5))/12 for n in range(25150)]

for _ in range(eval(input())):
	n = int(input())
	pos = bisect(result,n)
	if pos <= 1:
		print("0\nDraw")
	elif pos&1:
		print(pos-1)
		print("Ketan")
	else:
		print(pos-1)
		print("Dhruv")