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: interview

Starter code:

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


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()

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


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


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


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

from math import sqrt as S 
for _ in range(int(input())):
 n=int(input())
 a1=int(S(n))
 a2=n//a1
 #print(a1,a2)
 rem=n-a1*a2 
 # print(rem)
 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)