Problem description.
Winston and Royce love sharing memes with each other. They express the amount of seconds they laughed ar a meme as the number of ‘XD’ subsequences in their messages. Being optimization freaks, they wanted to find the string with minimum possible length and having exactly the given number of ‘XD’ subsequences.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases.
- Next T lines contains a single integer N, the no of seconds laughed.

-----Output-----
- 
For each input, print the corresponding string having minimum length. If there are multiple possible answers, print any.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 109
- 1 ≤ Sum of length of output over all testcases ≤ 5*105

-----Example-----
Input:
1
9

Output:
XXXDDD

-----Explanation-----
Some of the possible strings are - XXDDDXD,XXXDDD,XDXXXDD,XDXDXDD etc. Of these, XXXDDD is the smallest.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Combinatorics

Mathematics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
import sys
from math import *
t = int(input())
while t:
	l = []
	f = []
	s = ''
	n = int(input())
	if sqrt(n) % 1.0 == 0:
		y = sqrt(n)
		for x in range(int(y)):
			l.append('X')
		for x in range(int(y)):
			l.append('D')
		s = ''.join(l)
	else:
		count = 0
		for x in range(1, int(sqrt(n)) + 3):
			if x ** 2 > n:
				break
		x = x - 1
		b = x
		while b * x < n:
			b += 1
		for i in range(int(b)):
			l.append('X')
		for i in range(x):
			l.append('D')
		f = l.index('D')
		l.pop(f)
		l.insert(f - (b * x - n), 'D')
		s = ''.join(l)
	sys.stdout.write(s + '\n')
	t -= 1


from math import sqrt

def solve():
	n = int(input())
	k = int(sqrt(n))
	y = n - k * k
	z = y % k
	if z > 0:
		print('X' * z + 'D' + 'X' * (k - z) + 'D' * (k + y // k))
	else:
		print('X' * k + 'D' * (k + y // k))
t = int(input())
for tt in range(0, t):
	solve()


from math import *
t = int(input())
for test in range(t):
	n = int(input())
	p = int(sqrt(n))
	st = ''
	z = n - p * p
	st += p * 'X'
	x = z // p
	st += x * 'X'
	x = z % p
	st += (p - x) * 'D'
	if x > 0:
		st += 'X'
	st += x * 'D'
	print(st)


from math import *
for i in range(int(input())):
	n = int(input())
	k = int(sqrt(n))
	k = max(k, n // k)
	d = min(k, n // k)
	l = []
	for j in range(d):
		l.append('X')
	for j in range(k):
		l.append('D')
	p = n % k
	if p != 0:
		l.insert(-p, 'X')
	print(''.join(l))


t = int(input())
for j in range(t):
	n = int(input())
	last_d = int(n ** 0.5)
	one_d = n % last_d
	if one_d == 0:
		print((last_d - one_d) * 'X' + n // last_d * 'D')
	else:
		print(one_d * 'X' + 'D' + (last_d - one_d) * 'X' + n // last_d * 'D')


t = int(input())
for i in range(t):
	n = int(input())
	r = int(n ** 0.5)
	d = n - r * r
	m = d % r
	print('X' * m + 'D' * (m > 0) + 'X' * (r - m) + 'D' * (r + d // r))


t = int(input())
while t != 0:
	t = t - 1
	x = int(input())
	r = x ** 0.5
	r = int(r)
	n = x // r
	b = x % r
	if r < n:
		(r, n) = (n, r)
	st = 'X' * b + 'D' * bool(b) + 'X' * (r - b) + 'D' * n
	print(st)


import math
t = int(input())
for test_case in range(t):
	n = int(input())
	square_root = int(math.sqrt(n))
	if math.sqrt(n) == square_root:
		print(square_root * 'X' + square_root * 'D')
		continue
	if n - square_root ** 2 <= square_root:
		print(square_root * 'X' + (square_root - (n - square_root ** 2)) * 'D' + 'X' + (n - square_root ** 2) * 'D')
		continue
	D_count = square_root + 1
	print(square_root * 'X' + (D_count - (n - square_root * D_count)) * 'D' + 'X' + (n - square_root * D_count) * 'D')


import math
for _ in range(int(input())):
	n = int(input())
	x = int(math.sqrt(n))
	remainder = n - x * x
	x1 = x2 = d1 = 0
	x1 += x
	x1 += remainder // x
	remainder = n % x
	string = 'X' * x1 + 'D' * (x - remainder) + 'X' * (remainder > 0) + 'D' * remainder
	print(string)


import math
t = int(input())
for tst in range(t):
	num = int(input())
	x = int(math.sqrt(num))
	y = num // x
	z = num % x
	ans = ''
	if z == 0:
		for tst in range(x):
			ans = ans + 'X'
		for tst in range(y):
			ans = ans + 'D'
	else:
		for tst in range(x):
			ans = ans + 'X'
		for tst in range(y):
			ans = ans + 'D'
		ans = ans[:-z] + 'X' + ans[-z:]
	print(ans)


from math import sqrt as S
for _ in range(int(input())):
	n = int(input())
	a1 = int(S(n))
	a2 = n // a1
	rem = n - a1 * a2
	ans = ['X'] * a1 + ['D'] * a2
	if rem:
		ans.insert(-rem, 'X')
	print(*ans, sep='')


T = int(input())
for _ in range(T):
	N = int(input())
	r = int(N ** 0.5)
	d = N - r * r
	print('X' * (d % r) + 'D' * (d % r > 0) + 'X' * (r - d % r) + 'D' * (r + d // r))


for _ in range(int(input())):
	n = int(input())
	s = int(n ** 0.5)
	x = s
	if s * (s + 1) <= n:
		d = s + 1
	else:
		d = s
	sum1 = x * d
	del x
	while sum1 < n:
		sum1 += d
	if sum1 > n:
		sum1 -= d
	print('X' * (sum1 // d) + 'D' * (d - n + sum1), end='')
	if n != sum1:
		print('X' + 'D' * (n - sum1))
	else:
		print()


def sol():
	n = int(input())
	temp = int(pow(n, 0.5))
	if pow(temp, 2) == n:
		string = 'X' * temp + 'D' * temp
		print(string.strip())
		return
	else:
		string = list('X' * temp + 'D' * temp)
		l = n - pow(temp, 2)
		temp2 = temp
		while l > temp2:
			string.append('D')
			temp2 += 1
			l -= temp
		string.insert(-l, 'X')
		print(''.join(string))
for _ in range(int(input())):
	sol()


for _ in range(int(input())):
	n = int(input())
	print('X' * (int(n ** 0.5) + (n - int(n ** 0.5) * int(n ** 0.5)) // int(n ** 0.5)) + 'D' * (int(n ** 0.5) - n % int(n ** 0.5)) + 'X' * (n % int(n ** 0.5) > 0) + 'D' * (n % int(n ** 0.5)))


tc = int(input())
for test in range(tc):
	n = int(input())
	ln = int(n ** 0.5)
	string = ln * ['X'] + ln * ['D']
	pr_ln = ln * ln
	if n - ln * ln > ln:
		string += ['D']
		pr_ln += ln
	if pr_ln != n:
		string.insert(pr_ln - n, 'X')
	print(''.join(string))


for _ in range(int(input())):
	z = int(input())
	sqr = int(z ** 0.5)
	(a, c) = divmod(z, sqr)
	print(['X' * a + (sqr - c) * 'D' + 'X' + c * 'D', 'X' * a + 'D' * sqr][c == 0])


import math
t = int(input())
for _ in range(t):
	a = int(input())
	sq = math.ceil(math.sqrt(a))
	sqv = sq ** 2
	XS = ['X'] * sq
	DS = ['D'] * sq
	diff = sqv - a
	quo = diff // sq
	rem = diff % sq
	XS = XS[quo + (rem > 0):]
	if rem > 0:
		DS.insert(rem, 'X')
	print(''.join(XS + DS))


t = int(input())
for si in range(t):
	n = int(input())
	u = int(n ** (1 / 2))
	v = u + 1
	if u * u == n:
		print('X' * u + 'D' * u)
	elif v * v == n:
		print('X' * v + 'D' * v)
	else:
		k = v * v - u * u
		k = k - 1
		k = int(k / 2)
		if n > u * u + k:
			s1 = 'X' * k
			s2 = 'D' * (v * v - n) + 'X'
			s3 = (v - (v * v - n)) * 'D'
			print(s1 + s2 + s3)
		else:
			s1 = (n - u * u) * 'X' + 'D'
			s2 = 'X' * (u - (n - u * u))
			s3 = 'D' * u
			print(s1 + s2 + s3)


from math import sqrt
a1 = int(input())
for i in range(a1):
	ca = int(input())
	cb = int(sqrt(ca))
	k1 = ca // cb
	k2 = ca % cb
	if ca % cb == 0:
		print('X' * k1 + 'D' * cb)
	else:
		print('X' * k1 + 'D' * (cb - k2) + 'X' + 'D' * k2)


import math
for _ in range(int(input())):
	n = int(input())
	x = int(math.sqrt(n))
	print('X' * (x + (n - x * x) // x) + 'D' * (x - n % x) + 'X' * (n % x > 0) + 'D' * (n % x))


import math as mt
test_case = int(input())
for test in range(test_case):
	n = int(input())
	x = int(mt.sqrt(n))
	remainder = n - x * x
	x1 = x2 = d1 = 0
	x1 += x
	x1 += remainder // x
	remainder = n % x
	string = 'X' * x1 + 'D' * (x - remainder) + 'X' * (remainder > 0) + 'D' * remainder
	print(string)


import math
for i in range(int(input())):
	a = int(input())
	b = int(math.sqrt(a))
	if a % b != 0:
		print('X' * (a // b) + 'D' * (b - a % b) + 'X' + 'D' * (a % b))
	else:
		print('X' * (a // b) + 'D' * b)


t = int(input())
for _ in range(t):
	n = int(input())
	ns = int(n ** 0.5)
	ns1 = n // ns
	nl = n % ns1
	for i in range(ns):
		print('X', end='')
	for i in range(ns1):
		if i == ns1 - nl:
			print('X', end='')
		print('D', end='')
	print('')


from math import floor, ceil, sqrt
for _ in range(int(input())):
	n = int(input())
	x = ceil(sqrt(n * 4))
	x -= 1
	z = floor(x ** 2 / 4)
	ans = []
	for i in range(x // 2):
		ans.append('X')
	for i in range(x - x // 2):
		ans.append('D')
	ans.insert(x - (n - z), 'X')
	print(''.join(ans))


from math import sqrt
t = int(input())

def insert_back(ans, index, str):
	index = len(ans) - index
	ans = ans[:index] + str + ans[index:]
	return ans
for _ in range(t):
	n = int(input())
	sq = int(sqrt(n))
	ans = sq * 'X' + sq * 'D'
	rem = n - sq * sq
	if rem is not 0:
		if rem <= sq:
			ans = insert_back(ans, rem, 'X')
		else:
			ans += 'D'
			ans = insert_back(ans, rem - sq, 'X')
	print(ans)


from math import sqrt as S
for _ in range(int(input())):
	n = int(input())
	a1 = int(S(n))
	a2 = n // a1
	rem = n - a1 * a2
	ans = ['X'] * a1 + ['D'] * a2
	if rem:
		ans.insert(-rem, 'X')
	print(*ans, sep='')
	maxi = 1
	for i in range(2, int(S(n)) + 1):
		if n % i == 0:
			maxi = max(maxi, i)


import math
for _ in range(int(input())):
	n = int(input())
	s = int(math.sqrt(n))
	k = n // s
	r = n % s
	p = n // k
	if r == 0:
		print('X' * k + 'D' * p)
	else:
		print('X' * r + 'D' + 'X' * (k - r) + 'D' * p)


from math import floor, sqrt
for t in range(int(input())):
	n = int(input())
	k = floor(sqrt(n))
	ell = n - k ** 2
	if ell == 2 * k:
		print(k * 'X' + (k + 2) * 'D')
	elif ell >= k:
		r = ell - k
		print(r * 'X' + ('D' if r > 0 else '') + (k - r) * 'X' + (k + 1) * 'D')
	else:
		print(ell * 'X' + ('D' if ell > 0 else '') + (k - ell) * 'X' + k * 'D')


x = int(input())
for i in range(x):
	z = int(input())
	f = int(z ** 0.5)
	k = z // f
	m = z % f
	if m:
		k = 'X' * f + 'D' * (k - m) + 'X' + 'D' * m
	else:
		k = 'X' * f + 'D' * k
	print(k)


for _ in range(int(input())):
	number_of_laughts = int(input())
	string = 'XD'
	if number_of_laughts > 1:
		Xcount = 0
		c = 0
		xs = 1
		ds = 1
		for i in range(number_of_laughts):
			if i * i <= number_of_laughts:
				c = i
			else:
				break
		a = ''
		b = ''
		for _ in range(c):
			a = a + 'X'
			b = b + 'D'
		Xcount = c
		string = a + b
		difference = number_of_laughts - c * c
		if difference != 0:
			while difference > 0:
				if difference > c:
					string = string + 'D'
					difference -= c
				elif difference <= Xcount:
					one = string[:difference]
					two = string[difference:]
					string = one + 'D' + two
					difference -= difference
				else:
					one = string[:Xcount]
					two = string[Xcount:]
					string = one + 'D' + two
					difference -= X
	print(string)


import math
t = int(input())
for i in range(t):
	a = []
	n = int(input())
	c = int(math.sqrt(n))
	s = 'X' * c + 'D' * c
	if n - c ** 2 == 0:
		s = 'X' * c + 'D' * c
	else:
		z = c ** 2
		diff = n - z
		while diff >= c:
			s = s + 'D'
			diff -= c
		if diff > 0:
			s = s[:diff] + 'D' + s[diff:]
	print(s)


import math
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	k = int(math.sqrt(n))
	a = 'X' * k + 'D' * k
	g = n - k * k
	y = len(a) - g
	if g != 0 and k <= y:
		a = a[:y] + 'X' + a[y:]
	elif g != 0 and k > y:
		a = a[:] + 'D'
		x = k
		d = k + 1
		an = n - x * d
		u = len(a) - an
		a = a[:u] + 'X' + a[u:]
	print(a)


import math
for _ in range(int(input())):
	n = int(input())
	j = int(math.sqrt(n))
	if j * j == n:
		print('X' * j + 'D' * j)
		continue
	if n == 3:
		print('XDXD')
		continue
	if n == 2:
		print('XDD')
		continue
	if n == 1:
		print('XD')
		continue
	if n - j * j <= j:
		print('X' * (n - j * j) + 'D' + 'X' * (j - (n - j * j)) + 'D' * j)
	else:
		j += 1
		print('X' * (j - (j * j - n)) + 'D' + 'X' * (j - (j - (j * j - n))) + 'D' * (j - 1))


from sys import stdin
from math import sqrt, floor
for _ in range(int(stdin.readline().strip())):
	n = int(stdin.readline().strip())
	sqroot = sqrt(n)
	if sqroot % 1 > 0:
		(l, u) = (floor(sqroot), round(sqroot))
		diff = n - l * u
		print('X' * diff + 'D' + 'X' * (l - diff) + 'D' * u)
	else:
		sqroot = int(sqroot)
		print('X' * sqroot + 'D' * sqroot)


import math
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	x = math.ceil(n ** 0.5)
	dif = x * x - n
	if dif < x:
		print('X' * (x - 1) + 'D' * dif + 'X' + 'D' * (x - dif))
	else:
		dif = dif - x
		print('X' * (x - 1) + 'D' * dif + 'X' + 'D' * (x - dif - 1))


def string(q):
	abc = ''
	ef = ''
	for w in range(q):
		abc = abc + 'X'
		ef = ef + 'D'
	return abc + ef
t = int(input())
for q in range(t):
	n = int(input())
	l = int(n ** (1 / 2))
	if l == n ** (1 / 2):
		final = string(l)
	elif n > l * l + l:
		final = string(l + 1)
		rem = n - l * l - l
		i = len(final) - rem
		final = final[1:i] + 'X' + final[i:]
	else:
		final = string(l)
		rem = n - l * l
		i = len(final) - rem
		final = final[:i] + 'X' + final[i:]
	print(final)


import math
for _ in range(int(input())):
	n = int(input())
	p = n ** 0.5
	r = ''
	if p % 1 == 0:
		r += 'X' * int(p)
		r += 'D' * int(p)
	else:
		l = math.floor(p)
		if n <= l ** 2 + l:
			s = 2 * l + 1
			r += 'X' * l
			r += 'D' * (l ** 2 + l - n)
			r += 'X'
			r += 'D' * (n - l ** 2)
		else:
			r += 'X' * (l + 1)
			r += 'D' * ((l + 1) ** 2 - n - 1)
			r += 'X'
			r += 'D' * (n - l ** 2 - l)
	print(r)


from math import floor
from math import sqrt
t = int(input())

def nearest_sqrt(n):
	return floor(sqrt(n)) ** 2
while t > 0:
	nu = int(input())
	n = nearest_sqrt(nu)
	x = int(sqrt(n))
	d = x
	st = ''
	rem = abs(n - nu)
	if d >= rem:
		index = d - rem
		if rem != 0:
			d += 1
		for i in range(x):
			st += 'X'
		for i in range(d):
			if i == index and rem != 0:
				st += 'X'
			else:
				st += 'D'
	else:
		idx = 0
		while rem > 0 and (d + 1) * x <= nu:
			d += 1
			rem -= x
		if rem != 0:
			idx = d - rem
			d += 1
		for i in range(x):
			st += 'X'
		for j in range(d):
			if j == idx and rem != 0:
				st += 'X'
			else:
				st += 'D'
	print(st)
	t -= 1


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
for _ in range(ii()):
	n = ii()
	b = int(n ** 0.5)
	a = n // b
	c = n - a * b
	if c != 0:
		A = 'X' * a + (b - c) * 'D' + 'X' + c * 'D'
	else:
		A = 'X' * a + 'D' * b
	print(A)


t = int(input())
for z in range(t):
	n = int(input())
	k = int(n ** 0.5)
	Cx = k
	Cd = k
	if k * k < n:
		if k * k + k < n:
			Cd += 1
		Cx += 1
	mp = Cx * Cd
	ansArr = ['X'] * Cx + ['D'] * Cd
	if mp != n:
		shif = (mp - n) // (Cd - 1)
		ansArr[Cx - shif:Cx] = ['D'] * shif
		ansArr[Cx + Cd - shif - 1:-1] = ['X'] * shif
		shif = (mp - n) % (Cd - 1)
		if shif:
			idx = ansArr.index('D')
			ansArr[idx - 1] = 'D'
			ansArr[idx - 1 + shif] = 'X'
	print(''.join(ansArr))


from math import sqrt
from math import floor
t = int(input())

def main():
	n = int(input())
	root = floor(sqrt(n))
	sqr = root * root
	if sqr == n:
		print('X' * root + 'D' * root)
		return
	nxt_sqr = (root + 1) * (root + 1)
	diff_bw_sqr = nxt_sqr - sqr
	half_of_diff = diff_bw_sqr // 2
	string = 'X' * root + 'D' * root
	l_string = list(string)
	diff = n - sqr
	if diff < diff_bw_sqr // 2:
		l_string.insert(-diff, 'X')
	else:
		l_string.insert(0, 'X')
		l_string.insert(diff - half_of_diff, 'D')
	if l_string[0] == 'D':
		l_string = l_string[1:]
	print(''.join(l_string))
for i in range(t):
	main()