Problem: This is an interactive problem. Don't forget to flush output after printing queries using cout.flush() or fflush(stdout) in C++ or similar functions in other programming languages.

There are n gift boxes in a row, numbered from 1 to n from left to right. It's known that exactly k of them contain valuable gifts — other boxes contain just lucky stones. All boxes look the same and differ only in weight. All boxes with stones have the same weight and are strictly heavier than boxes with valuable items. But valuable gifts may be different, so the boxes with valuable items may have different weights.

You can ask no more than 50 queries (printing an answer doesn't count). By each query you can compare total weights of two non-intersecting subsets of boxes a_1, a_2, ..., a_{k_a} and b_1, b_2, ..., b_{k_b}. In return you'll get one of four results:

  * FIRST, if subset a_1, a_2, ..., a_{k_a} is strictly heavier; 
  * SECOND, if subset b_1, b_2, ..., b_{k_b} is strictly heavier; 
  * EQUAL, if subsets have equal total weights; 
  * WASTED, if the query is incorrect or the limit of queries is exceeded. 



Using such queries (or, maybe, intuition) find the box with a valuable gift with the minimum index.

Input

The input consists of several cases. In the beginning, you receive the integer T (1 ≤ T ≤ 500) — the number of test cases.

At the beginning of each test case, you receive two integers n and k (2 ≤ n ≤ 1000, 1 ≤ k ≤ n/2) — the number of boxes in a row and the number of boxes with valuable gifts.

It's guaranteed that the order of boxes is fixed beforehand and that the sum of n in one test doesn't exceed 1000.

Output

For each test case print the minimum index among all boxes with a valuable gift in the following format: "! x" where x (1 ≤ x ≤ n) — the index of the box.

Interaction

Print each query in three lines. In the first line print the sizes of subset in the following format: "? k_a k_b" where k_a and k_b (1 ≤ k_a, k_b ≤ n; k_a + k_b ≤ n) — the corresponding sizes.

In the second line print k_a integers a_1, a_2, ..., a_{k_a} (1 ≤ a_i ≤ n; a_i ≠ a_j if i ≠ j) — indexes of boxes in the first subset.

In the third line print k_b integers b_1, b_2, ..., b_{k_b} (1 ≤ b_i ≤ n; b_i ≠ b_j if i ≠ j) — indexes of boxes in the second subset.

The subsets shouldn't intersect, i. e. a_i ≠ b_j for all i and j.

You'll receive one of four responses described above. In the case of WASTED stop your program to avoid getting random verdict instead of Wrong Answer.

Example

Input


2
2 1
-
-
-
FIRST
-
5 2
-
-
-
FIRST
-
-
-
SECOND
-
-
-
EQUAL
-

Output


-
-
? 1 1
1
2
-
! 2
-
? 1 1
1
2
-
? 2 3
4 2
1 3 5
-
? 1 1
4
5
-
! 1

Note

Additional separators "–" in the sample are used only to increase the readability of the sample. Don't print any unnecessary symbols or line breaks in your solution when you send it to the system.

Hacks are forbidden in this task.

Solution (in JAVA):

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

public class Main implements Runnable {
	boolean judge = false;
	FastReader scn;
	PrintWriter out;
	String INPUT = "";

	void solve() {
		int t = scn.nextInt();
		while (t-- > 0) {
			int n = scn.nextInt(), k = scn.nextInt();

			if (n < 5) {
				int stone = 1;
				for (int loop = 1; loop <= n; loop++) {
					for (int i = 1; i <= n; i++) {
						if (i == stone) {
							continue;
						}
						out.println("? 1 1");
						out.flush();
						out.println(stone);
						out.flush();
						out.println(i);
						out.flush();
						String s = scn.next();
						if (s.equals("SECOND")) {
							stone = i;
						}
					}
				}
				int ans = 0;
				for(int i = 1; i <= n; i++) {
					if(i == stone) {
						continue;
					}
					out.println("? 1 1");
					out.flush();
					out.println(stone);
					out.flush();
					out.println(i);
					out.flush();
					String s = scn.next();
					if(s.equals("FIRST")) {
						ans = i;
						break;
					}
				}
				out.println("! " + ans);
				out.flush();
				continue;
			}

			HashSet<Integer> asks = new HashSet<Integer>();

			while (asks.size() != Math.min(n - 2, 23)) {
				int x = new Random().nextInt(n - 1) + 1;
				while (asks.contains(x)) {
					x = new Random().nextInt(n - 1) + 1;
				}
				asks.add(x);
			}

			int stone = n;
			for (int x : asks) {
				out.println("? 1 1");
				out.flush();
				out.println(stone);
				out.flush();
				out.println(x);
				out.flush();
				String s = scn.next();
				if (s.equals("SECOND")) {
					stone = x;
				}
				if (s.equals("WASTED")) {
					return;
				}
			}

			// check 1
			if (stone != 1) {
				out.println("? 1 1");
				out.flush();
				out.println(stone);
				out.flush();
				out.println(1);
				out.flush();
				String s = scn.next();
				if (s.equals("FIRST")) {
					out.println("! " + 1);
					out.flush();
					continue;
				}
			}

			int range = 1;
			for (int len = 1; 2 * len <= n; len += len) {
				out.println("? " + len + " " + len);
				out.flush();
				for (int i = 1; i <= len; i++) {
					out.print(i + " ");
				}
				out.println();
				out.flush();
				for (int i = 1; i <= len; i++) {
					out.print(len + i + " ");
				}
				out.println();
				out.flush();

				String s = scn.next();
				if (s.equals("FIRST")) {
					break;
				}
				range = 2 * len;
			}

			int l = 1, r = Math.min(range, n - range), ans = -1;
			while (l <= r) {
				int len = (l + r) >> 1;
				out.println("? " + len + " " + len);
				out.flush();
				for (int i = 1; i <= len; i++) {
					out.print(i + " ");
				}
				out.println();
				out.flush();
				for (int i = 1; i <= len; i++) {
					out.print(range + i + " ");
				}
				out.println();
				out.flush();

				String s = scn.next();
				if (s.equals("FIRST")) {
					ans = range + len;
					r = len - 1;
				} else {
					l = len + 1;
				}
			}
			out.println("! " + ans);
			out.flush();
		}
	}

	public void run() {
		long time = System.currentTimeMillis();
		boolean oj = System.getProperty("ONLINE_JUDGE") != null || judge;
		out = new PrintWriter(System.out);
		scn = new FastReader(oj);
		solve();
		out.flush();
		if (!oj) {
			System.out.println(Arrays.deepToString(new Object[] { System.currentTimeMillis() - time + " ms" }));
		}
	}

	public static void main(String[] args) {
		new Thread(null, new Main(), "Main", 1 << 28).start();
	}

	class FastReader {
		InputStream is;

		public FastReader(boolean onlineJudge) {
			is = onlineJudge ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		}

		byte[] inbuf = new byte[1024];
		public int lenbuf = 0, ptrbuf = 0;

		int readByte() {
			if (lenbuf == -1)
				throw new InputMismatchException();
			if (ptrbuf >= lenbuf) {
				ptrbuf = 0;
				try {
					lenbuf = is.read(inbuf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return -1;
			}
			return inbuf[ptrbuf++];
		}

		boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		int skip() {
			int b;
			while ((b = readByte()) != -1 && isSpaceChar(b))
				;
			return b;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		char nextChar() {
			return (char) skip();
		}

		String next() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		String nextLine() {
			int b = skip();
			StringBuilder sb = new StringBuilder();
			while ((!isSpaceChar(b) || b == ' ')) { // when nextLine, (isSpaceChar(b) && b != ' ')
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		char[] next(int n) {
			char[] buf = new char[n];
			int b = skip(), p = 0;
			while (p < n && !(isSpaceChar(b))) {
				buf[p++] = (char) b;
				b = readByte();
			}
			return n == p ? buf : Arrays.copyOf(buf, p);
		}

		int nextInt() {
			int num = 0, b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}

			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}

		long nextLong() {
			long num = 0;
			int b;
			boolean minus = false;
			while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
				;
			if (b == '-') {
				minus = true;
				b = readByte();
			}

			while (true) {
				if (b >= '0' && b <= '9') {
					num = num * 10 + (b - '0');
				} else {
					return minus ? -num : num;
				}
				b = readByte();
			}
		}

		char[][] nextMatrix(int n, int m) {
			char[][] map = new char[n][];
			for (int i = 0; i < n; i++)
				map[i] = next(m);
			return map;
		}

		int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[][] next2DInt(int n, int m) {
			int[][] arr = new int[n][];
			for (int i = 0; i < n; i++) {
				arr[i] = nextIntArray(m);
			}
			return arr;
		}

		long[][] next2DLong(int n, int m) {
			long[][] arr = new long[n][];
			for (int i = 0; i < n; i++) {
				arr[i] = nextLongArray(m);
			}
			return arr;
		}

		int[] shuffle(int[] arr) {
			Random r = new Random();
			for (int i = 1, j; i < arr.length; i++) {
				j = r.nextInt(i);
				int c = arr[i];
				arr[i] = arr[j];
				arr[j] = c;
			}
			return arr;
		}

		long[] shuffle(long[] arr) {
			Random r = new Random();
			for (int i = 1, j; i < arr.length; i++) {
				j = r.nextInt(i);
				long c = arr[i];
				arr[i] = arr[j];
				arr[j] = c;
			}
			return arr;
		}

		int[] uniq(int[] arr) {
			arr = scn.shuffle(arr);
			Arrays.sort(arr);
			int[] rv = new int[arr.length];
			int pos = 0;
			rv[pos++] = arr[0];
			for (int i = 1; i < arr.length; i++) {
				if (arr[i] != arr[i - 1]) {
					rv[pos++] = arr[i];
				}
			}
			return Arrays.copyOf(rv, pos);
		}

		long[] uniq(long[] arr) {
			arr = scn.shuffle(arr);
			Arrays.sort(arr);
			long[] rv = new long[arr.length];
			int pos = 0;
			rv[pos++] = arr[0];
			for (int i = 1; i < arr.length; i++) {
				if (arr[i] != arr[i - 1]) {
					rv[pos++] = arr[i];
				}
			}
			return Arrays.copyOf(rv, pos);
		}

		int[] reverse(int[] arr) {
			int l = 0, r = arr.length - 1;
			while (l < r) {
				arr[l] = arr[l] ^ arr[r];
				arr[r] = arr[l] ^ arr[r];
				arr[l] = arr[l] ^ arr[r];
				l++;
				r--;
			}
			return arr;
		}

		long[] reverse(long[] arr) {
			int l = 0, r = arr.length - 1;
			while (l < r) {
				arr[l] = arr[l] ^ arr[r];
				arr[r] = arr[l] ^ arr[r];
				arr[l] = arr[l] ^ arr[r];
				l++;
				r--;
			}
			return arr;
		}

		int[] compress(int[] arr) {
			int n = arr.length;
			int[] rv = Arrays.copyOf(arr, n);
			rv = uniq(rv);
			for (int i = 0; i < n; i++) {
				arr[i] = Arrays.binarySearch(rv, arr[i]);
			}
			return arr;
		}

		long[] compress(long[] arr) {
			int n = arr.length;
			long[] rv = Arrays.copyOf(arr, n);
			rv = uniq(rv);
			for (int i = 0; i < n; i++) {
				arr[i] = Arrays.binarySearch(rv, arr[i]);
			}
			return arr;
		}

		void deepFillInt(Object array, int val) {
			if (!array.getClass().isArray()) {
				throw new IllegalArgumentException();
			}
			if (array instanceof int[]) {
				int[] intArray = (int[]) array;
				Arrays.fill(intArray, val);
			} else {
				Object[] objArray = (Object[]) array;
				for (Object obj : objArray) {
					deepFillInt(obj, val);
				}
			}
		}

		void deepFillLong(Object array, long val) {
			if (!array.getClass().isArray()) {
				throw new IllegalArgumentException();
			}
			if (array instanceof long[]) {
				long[] intArray = (long[]) array;
				Arrays.fill(intArray, val);
			} else {
				Object[] objArray = (Object[]) array;
				for (Object obj : objArray) {
					deepFillLong(obj, val);
				}
			}
		}
	}
}