Problem: [MisoilePunch♪ - 彩](https://www.youtube.com/watch?v=5VleIdkEeak)

This is an interactive problem!

On a normal day at the hidden office in A.R.C. Markland-N, Rin received an artifact, given to her by the exploration captain Sagar.

After much analysis, she now realizes that this artifact contains data about a strange flower, which has existed way before the New Age. However, the information about its chemical structure has been encrypted heavily.

The chemical structure of this flower can be represented as a string p. From the unencrypted papers included, Rin already knows the length n of that string, and she can also conclude that the string contains at most three distinct letters: "C" (as in Carbon), "H" (as in Hydrogen), and "O" (as in Oxygen).

At each moment, Rin can input a string s of an arbitrary length into the artifact's terminal, and it will return every starting position of s as a substring of p.

However, the artifact has limited energy and cannot be recharged in any way, since the technology is way too ancient and is incompatible with any current A.R.C.'s devices. To be specific:

  * The artifact only contains 7/5 units of energy. 
  * For each time Rin inputs a string s of length t, the artifact consumes (1)/(t^2) units of energy. 
  * If the amount of energy reaches below zero, the task will be considered failed immediately, as the artifact will go black forever. 



Since the artifact is so precious yet fragile, Rin is very nervous to attempt to crack the final data. Can you give her a helping hand?

Interaction

The interaction starts with a single integer t (1 ≤ t ≤ 500), the number of test cases. The interaction for each testcase is described below:

First, read an integer n (4 ≤ n ≤ 50), the length of the string p.

Then you can make queries of type "? s" (1 ≤ |s| ≤ n) to find the occurrences of s as a substring of p.

After the query, you need to read its result as a series of integers in a line:

  * The first integer k denotes the number of occurrences of s as a substring of p (-1 ≤ k ≤ n). If k = -1, it means you have exceeded the energy limit or printed an invalid query, and you need to terminate immediately, to guarantee a "Wrong answer" verdict, otherwise you might get an arbitrary verdict because your solution will continue to read from a closed stream.
  * The following k integers a_1, a_2, …, a_k (1 ≤ a_1 < a_2 < … < a_k ≤ n) denote the starting positions of the substrings that match the string s.



When you find out the string p, print "! p" to finish a test case. This query doesn't consume any energy. The interactor will return an integer 1 or 0. If the interactor returns 1, you can proceed to the next test case, or terminate the program if it was the last testcase.

If the interactor returns 0, it means that your guess is incorrect, and you should to terminate to guarantee a "Wrong answer" verdict.

Note that in every test case the string p is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.

After printing any query do not forget to print end of line and flush the output. Otherwise, you might get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see the documentation for other languages.



Hacks

For hack, use the following format. Note that you can only hack with one test case:

The first line should contain a single integer t (t = 1).

The second line should contain an integer n (4 ≤ n ≤ 50) — the string's size.

The third line should contain a string of size n, consisting of characters "C", "H" and "O" only. This is the string contestants will have to find out.

Examples

Input


1
4

2 1 2

1 2

0

1

Output




? C

? CH

? CCHO

! CCHH



Input


2
5

0

2 2 3

1
8

1 5

1 5

1 3

2 1 2

1

Output




? O

? HHH

! CHHHH


? COO

? COOH

? HCCOO

? HH

! HHHCCOOH

Note

Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Akisolution {
	public static Scanner sc = new Scanner(System.in);

	public static class CPPString {
		// as the Java String is insanely cryptic to modify
		public char[] arr;

		public CPPString() {}
		public CPPString(String str) {this.arr = str.toCharArray();}
		public CPPString(char[] ca) {this.arr = ca;}
		public CPPString(CPPString other) {
			this.arr = new char[other.arr.length];
			for (int i=0; i<other.arr.length; i++) this.arr[i] = other.arr[i];
		}
		public void resize(int length, char defaultChar) {
			this.arr = new char[length];
			for (int i=0; i<length; i++) this.arr[i] = defaultChar;
		}
		public int size() {return this.arr.length;}
		public CPPString substr(int L, int len) {
			// get substring [L, L+len)
			char[] res = new char[len];
			for (int i=0; i<len; i++) res[i] = this.arr[L+i];
			return new CPPString(res);
		}
		public CPPString add(char ch) {
			char[] new_ca = new char[this.arr.length + 1]; new_ca[this.arr.length] = ch;
			for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
			return new CPPString(new_ca);
		}
		public CPPString add(CPPString other) {
			char[] new_ca = new char[this.arr.length + other.arr.length];
			for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
			for (int i=0; i<other.arr.length; i++) new_ca[this.arr.length + i] = other.arr[i];
			return new CPPString(new_ca);
		}

		@Override
		public String toString() {return new String(arr);}
	}

	public static int n, L, minID;
	public static CPPString s;

	public static void fill(int id, char c) {
		if (s.arr[id] == 'L') L--;
		s.arr[id] = c;
		minID = (minID < id) ? minID : id;
	}

	public static void query(char cmd, CPPString str) {
		System.out.println(cmd + " " + str); System.out.flush();
		System.err.println(cmd + " " + str);
		if (cmd == '?') {
			int k = sc.nextInt();
			assert (k != -1);
			int[] a = new int[k];
			for (int index = 0; index < k; index++) {
				a[index] = sc.nextInt() - 1;
				for (int i=0; i<str.size(); i++) {
					assert (s.arr[a[index]+i] == 'L' || s.arr[a[index]+i] == str.arr[i]);
					fill(a[index]+i, str.arr[i]);
				}
			}
		}
		else if (cmd == '!') {
			int correct = sc.nextInt();
			assert (correct == 1);
		}
	}

	public static void query(char cmd, String str) {
		query(cmd, new CPPString(str));
	}

	public static void Input() {
		n = sc.nextInt(); s = new CPPString();
		L = n; minID = n; s.resize(n, 'L');
	}

	public static void Solve() {
		query('?', "CH"); query('?', "CO");
		query('?', "HC"); query('?', "HO");
		if (L == n) {
			// the string exists in form O...OX...X, with X=C or X=H
			// or it's completely mono-character
			query('?', "CCC");
			if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
			else {
				query('?', "HHH");
				if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
				else {
					query('?', "OOO");
					if (minID == n) {
						// obviously n=4
						query('?', "OOCC");
						if (minID == n) {fill(0, 'O'); fill(1, 'O'); fill(2, 'H'); fill(3, 'H');}
					}
					if (s.arr[n-1] == 'L') {
						CPPString t = new CPPString(s); t.arr[n-1] = 'C';
						if (t.arr[n-2] == 'L') t.arr[n-2] = 'C';
						query('?', t);
						if (s.arr[n-1] == 'L') {
							fill(n-1, 'H');
							if (s.arr[n-2] == 'L') fill(n-2, 'H');
						}
					}
				}
			}
		}
		else {
			int maxID = minID; while (maxID < n-1 && s.arr[maxID+1] != 'L') maxID++;
			for (int i=minID-1; i>=0; i--) {
				query('?', s.substr(i+1, 1).add(s.substr(minID, maxID-minID+1)));
				if (minID != i) {
					for (int x=0; x<=i; x++) fill(x, 'O');
					break;
				}
			}
			int nextFilled;
			for (int i=maxID+1; i<n; i++) {
				if (s.arr[i] != 'L') continue;
				nextFilled = i;
				while (nextFilled < n && s.arr[nextFilled] == 'L') nextFilled++;
				query('?', s.substr(0, i).add(s.arr[i-1]));
				if (s.arr[i] == 'L') {
					if (s.arr[i-1] != 'O') fill(i, 'O');
					else {
						if (nextFilled == n) {
							query('?', s.substr(0, i).add('C'));
							if (s.arr[i] == 'L') fill(i, 'H');
							for (int x=i+1; x<nextFilled; x++) fill(x, s.arr[i]);
						}
						else for (int x=i; x<nextFilled; x++) fill(x, s.arr[nextFilled]);
						i = nextFilled - 1;
					}
				}
			}
		}
		query('!', s);
	}

	public static void main(String[] args) {
		int T = sc.nextInt();
		while (T-- > 0) {Input(); Solve();}
	}
}