Chef Ciel wants to put a fancy neon signboard over the entrance of her restaurant. She has not enough money to buy the new one so she bought some old neon signboard through the internet. Ciel was quite disappointed when she received her order - some of its letters were broken. But she realized that this is even better - she could replace each broken letter by any letter she wants. So she decided to do such a replacement that the resulting signboard will contain the word "CHEF" as many times as possible.
We can model the signboard as a string S having capital letters from 'A' to 'Z', inclusive, and question marks '?'. Letters in the string indicate the intact letters at the signboard, while question marks indicate broken letters. So Ciel will replace each question mark with some capital letter and her goal is to get the string that contains as many substrings equal to "CHEF" as possible. If there exist several such strings, she will choose the lexicographically smallest one.
Note 1. The string S = S1...SN has the substring "CHEF" if for some i we have SiSi+1Si+2Si+3 = "CHEF". The number of times "CHEF" is the substring of S is the number of those i for which SiSi+1Si+2Si+3 = "CHEF".
Note 2. The string A = A1...AN is called lexicographically smaller than the string B = B1...BN if there exists K from 1 to N, inclusive, such that Ai = Bi for i = 1, ..., K-1, and AK < BK. In particular, A is lexicographically smaller than B if A1 < B1. We compare capital letters by their positions in the English alphabet. So 'A' is the smallest letter, 'B' is the second smallest letter, ..., 'Z' is the largest letter.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains a string S.

-----Output-----
For each test case, output a single line containing the content of the signboard Chef Ciel will come up with. That is you should output the lexicographically smallest string that could be obtained from the input string by replacing all its question marks by some capital letters and having as many substrings equal to "CHEF" as possible.

-----Constraints-----
- 1 ≤ T ≤ 2013
- 1 ≤ length of S ≤ 2013
- Each character in S is either a capital letter from 'A' to 'Z', inclusive, or the question mark '?'.

-----Example-----
Input:
5
????CIELIS???E?
????CIELISOUR???F
T?KEITE?SY
????????
???C???

Output:
CHEFCIELISACHEF
CHEFCIELISOURCHEF
TAKEITEASY
CHEFCHEF
AAACHEF

-----Explanation -----
Example Case 1. Here the resulting string can have at most 2 substrings equal to "CHEF". For example, some possible such strings are:

- CHEFCIELISACHEF
- CHEFCIELISQCHEF
- CHEFCIELISZCHEF
However, lexicographically smallest one is the first one.

Example Case 3. Here the resulting string cannot have "CHEF" as its substring. Therefore, you must simply output the lexicographically smallest string that can be obtained from the given one by replacing question marks with capital letters.

Difficulty: interview

Starter code:

Solutions:
from math import gcd
import sys
input=lambda : sys.stdin.readline().strip()
c=lambda x: 10**9 if(x=="?") else int(x)
def main():
 for _ in range(int(input())):
  s=list(input())[::-1]
  l=['F','E','H','C']
  i=0
  while(i<len(s)):
   if(i+3<len(s)):
    f=True
    for j in range(i,i+4):
     if(l[j-i]==s[j] or s[j]=='?'):
      pass
     else:
      f=False
      break
    if(f):
     for j in range(i,i+4):
      s[j]=l[j-i]
    if(s[i]=="?"):
     s[i]='A'
   else:
    if(s[i]=="?"):
     s[i]="A"
   i+=1
  print(*s[::-1],sep='')

   

main()

# cook your dish here
t=int(input())
for _ in range(t):
 s=input()
 if len(s)<4:
  for i in range(len(s)):
   if s[i]=='?':
    s=s[:i]+'A'+s[i+1:]
 else:
  
  for i in range(len(s)-1,-1,-1):
   x=s[i-3:i+1]
   
   # print(x)
   xx='CHEF'
   for j in range(len(x)):
    if x[j]=='?':
     x=x[:j]+xx[j]+x[j+1:]
   
   if x=='CHEF':
    s=s[:i-3]+'CHEF'+s[i+1:]
  for i in range(len(s)):
   if s[i]=='?':
    s=s[:i]+'A'+s[i+1:]
 print(s)
 # print()


# cook your dish here
for i in range(int(input())):
 s = list(input())
 for i in range(len(s)-4,-1,-1):
  c = 0
  if s[i] == "?":
   c+=1
  else:
   if s[i] == "C":
    c+=1
   else:
    continue
   
  if s[i+1] == "?":
   c+=1
  else:
   if s[i+1] == "H":
    c+=1
   else:
    continue
   
  if s[i+2] == "?":
   c+=1
  else:
   if s[i+2] == "E":
    c+=1
   else:
    continue
   
  if s[i+3] == "?":
   c+=1
  else:
   if s[i+3] == "F":
    c+=1
   else:
    continue
  if c == 4:
   s[i] = "C"
   s[i+1] = "H"
   s[i+2] = "E"
   s[i+3] = "F"
 for j in range(len(s)-1,-1,-1):
  if s[j] == "?":
   s[j] = "A"
 print(*s,sep="")


def isPossible(l):
 if ((l[0]=='C' or l[0]=='?') and (l[1]=='H' or l[1]=='?')
 and (l[2]=='E' or l[2]=='?') and (l[3]=='F' or l[3]=='?')):
  return True
 else:
  return False


T = int(input())
ans = []

for _ in range(T):
 S = list(input())

 N = len(S)
 for i in range(N-1,2,-1):
  if(isPossible(S[i-3:i+1])):
   S[i] = 'F'
   S[i-1] = 'E'
   S[i-2] = 'H'
   S[i-3] = 'C'
 for i in range(N):
  if(S[i]=='?'):
   S[i] = 'A'

 s = ''
 for i in S:
  s += i
 ans.append(s)

for i in ans:
 print(i)

t = int(input())
for T in range(t):
 l = list(input())

 ind = len(l)
 ans = 0
 while(ind > 3):
  val = l[ind - 4: ind]
  
  if val.count('?') == 0:
   ind -= 1
   continue
  
  s1 = ''.join(val)
  if s1 == 'CHEF':
   ind -= 4
   continue

  flag = 0
  if val.count('?') > 0:
   if val[0] != '?' and val[0] != 'C':
    flag = -1
   if val[0 + 1] != '?' and val[0 + 1] != 'H':
    flag = -1
   if val[0 + 2] != '?' and val[0 + 2] != 'E':
    flag = -1
   if val[0 + 3] != '?' and val[0 + 3] != 'F':
    flag = -1

  if flag == 0:
   l[ind - 4] = 'C'
   l[ind - 3] = 'H'
   l[ind - 2] = 'E'
   l[ind - 1] = 'F'
   ind -= 4
   continue

  
  ind -= 1
  
 n_string = ''.join(l)
 n_string = n_string.replace('?', 'A')
 print(n_string)


# cook your dish here
def replace_if_possible(i):
 nonlocal string
 if (string[i] != '?' and string[i] != 'C') or \
  (string[i+1] != '?' and string[i+1] != 'H') or \
  (string[i+2] != '?' and string[i+2] != 'E') or \
  (string[i+3] != '?' and string[i+3] != 'F'):
   return
 
 string[i:i+4] = 'CHEF'


t = int(input())
for _ in range(t):
 string = list(input())
 
 i = len(string) - 4
 while i >= 0:
  replace_if_possible(i)
  i -= 1
 
 for i in range(len(string)):
  if string[i] == '?':
   string[i] = 'A'
   
 print("".join(string))

# cook your dish here
def check(arr):
 dic={0:'C',1:'H',2:'E',3:'F'}
 for i in range(4):
  if arr[i] != '?':
   if arr[i]!=dic[i]:
    return -1
 for i in range(4):
  if arr[i]=='?':
   arr[i]=dic[i]
 return arr

t=int(input())
for _ in range(t):
 arr=input()
 arr=list(arr)
 i=len(arr)
 
 if i<4:
  for k in range(i):
   if arr[k]=='?':
    arr[k]='A'
 
 
 while i>3:
  if '?' in arr[i-4:i]:
   if check(arr[i-4:i])==-1:
    i-=1
    continue
   else:
    arr[i-4:i]=check(arr[i-4:i])
    i-=3
  i-=1
 for k in range(len(arr)):
  if arr[k]=='?':
   arr[k]='A'
 
   
 res=''
 for ele in arr:
  res+=ele
 print(res)
 
    

  
  
  
  
 


# cook your dish here
possiblity ={'?EHC','??H?','?E??','?EH?','F?H?','???C','?E?C','FE?C',
    'F???','FE??','????','FEH?','??HC','F??C','F?HC'}
for _ in range(int(input())):
 st =input()
 st =st[::-1]
 ln =len(st)
 ans =['0']*ln
 i = ln-1
 i =0
 while i+3<ln:
  if st[i:i+4] in possiblity:
   ans[i:i+4] = ['F','E','H','C']
   i += 4
  else:
   ans[i] = st[i]
   i +=1
 if i<len(st):
  ans[i:] = st[i:]
 for i in range(ln):
  if ans[i] == '?':
   ans[i] = 'A'
 print(*ans[::-1],sep='')