Problem: This is the easy version of the problem. The only difference is that here k=2. You can make hacks only if both the versions of the problem are solved.

This is an interactive problem.

Every decimal number has a base k equivalent. The individual digits of a base k number are called k-its. Let's define the k-itwise XOR of two k-its a and b as (a + b)mod k.

The k-itwise XOR of two base k numbers is equal to the new number formed by taking the k-itwise XOR of their corresponding k-its. The k-itwise XOR of two decimal numbers a and b is denoted by a⊕_{k} b and is equal to the decimal representation of the k-itwise XOR of the base k representations of a and b. All further numbers used in the statement below are in decimal unless specified. When k = 2 (it is always true in this version), the k-itwise XOR is the same as the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

You have hacked the criminal database of Rockport Police Department (RPD), also known as the Rap Sheet. But in order to access it, you require a password. You don't know it, but you are quite sure that it lies between 0 and n-1 inclusive. So, you have decided to guess it. Luckily, you can try at most n times without being blocked by the system. But the system is adaptive. Each time you make an incorrect guess, it changes the password. Specifically, if the password before the guess was x, and you guess a different number y, then the system changes the password to a number z such that x⊕_{k} z=y. Guess the password and break into the system.

Input

The first line of input contains a single integer t (1≤ t≤ 10 000) denoting the number of test cases. t test cases follow.

The first line of each test case contains two integers n (1≤ n≤ 2⋅ 10^5) and k (k=2).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅ 10^5.

Interaction

For each test case, first read two integers n and k. Then you may ask up to n queries.

For each query, print a single integer y (0≤ y≤ 2⋅ 10^7). Let the current password be x. After that, read an integer r.

If x=y, you will read r=1 and the test case is solved. You must then continue solving the remaining test cases.

Else, you will read r=0. At this moment the password is changed to a number z such that x⊕_{k} z=y.

After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get the Idleness limit exceeded verdict.

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 documentation for other languages. 



If you ask an invalid query or exceed n queries, you will read r=-1 and you will receive the Wrong Answer verdict. Make sure to exit immediately to avoid unexpected verdicts.

Note that the interactor is adaptive. That is, the original password is not fixed in the beginning and may depend on your queries. But it is guaranteed that at any moment there is at least one initial password such that all the answers to the queries are consistent.

Hacks:

To use hacks, use the following format of tests:

The first line should contain a single integer t (1≤ t≤ 10 000) — the number of test cases.

The first and only line of each test case should contain two integers n (1≤ n≤ 2⋅ 10^5) and k (k=2) denoting the number of queries and the base respectively. The optimal original password is automatically decided by the adaptive interactor.

You must ensure that the sum of n over all test cases does not exceed 2⋅ 10^5.

Example

Input


1
5 2

0

0

1


Output


3

4

5

Note

In the example test case, the hidden password is 2.

The first query is 3. It is not equal to the current password. So, 0 is returned, and the password is changed to 1 since 2⊕_2 1=3.

The second query is 4. It is not equal to the current password. So, 0 is returned, and the password is changed to 5 since 1⊕_2 5=4.

The third query is 5. It is equal to the current password. So, 1 is returned, and the job is done.

Note that this initial password is taken just for the sake of explanation. When you submit, the interactor might behave differently because it is adaptive.

Solution (in JAVA):

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

public class Codeforces {
	// private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static FastReader sc=new FastReader();
	static long mod=1000000007;
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		PrintWriter out=new PrintWriter(System.out);
		StringBuffer sb=new StringBuffer();
		int t=I();
		while(t-->0)
		{
			int n=I();
			int k=I();
			int x=0;
			for(int i=0;i<n;i++){
				int p=i^x;
				out.println(p+"\n");
				out.flush();
				x=x^p;
				if(I()==1)break;
			}
		}
		out.print(sb.toString());
		out.close();
	}
	public static void DFS(ArrayList<Integer> arr[],int s,boolean visited[])
	{
		visited[s]=true;
		for(int i:arr[s]){
			if(!visited[i]){
				DFS(arr,i,visited);
			}
		}
	}
	public static int BS(long a[],long x,int ii,int jj)
	{
		// int n=a.length;
		int mid=0;
		int i=ii,j=jj;
		while(i<=j)
		{
			mid=(i+j)/2;
			if(a[mid]>x)
			j=mid-1;
			else if(a[mid]<=x)
			i=mid+1;
		}
		if(a[mid]>x && mid>ii)
		return mid-1;
		else
		return mid;
	}
	public static ArrayList<Integer> prime(int n)
	{
	    ArrayList<Integer> arr=new ArrayList<>();
	    boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
        prime[i] = true;
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
            arr.add(i);
        }
        return arr;
	}
	public static HashSet<Integer> primeSet(int n)
	{
	    HashSet<Integer> arr=new HashSet<>();
	    boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
        prime[i] = true;
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
            arr.add(i);
        }
        return arr;
	}

	// Fenwick / BinaryIndexed  Tree  USE IT - FenwickTree ft1=new FenwickTree(n);
	public static class FenwickTree
	{
		long farr[];
		int n;
		public FenwickTree(int c)
		{
			n=c+1;
			farr=new long[n];
		}
		public void update_range(int l,int r,long p)
		{
			update(l,p);
			update(r+1,(-1)*p);
		}
		public void update(int x,long p)
		{
			for(;x<n;x+=x&(-x))
			{
				farr[x]+=p;
			}
		}
		public long get(int x)
		{
			long ans=0;
			for(;x>0;x-=x&(-x))
			{
				ans=ans+farr[x];
			}
			return ans;
		}
	}

	//Disjoint Set Union
	public static class DSU
	{
	    static int par[],rank[];
	    public DSU(int c)
	    {
	        par=new int[c+1];
	        rank=new int[c+1];
	        for(int i=0;i<=c;i++)
	        {
	            par[i]=i;
	            rank[i]=0;
	        }
	    }
	    public static int find(int a)
	    {
	        if(a==par[a])
	        return a;
	        return par[a]=find(par[a]);
	    }
	    public static void union(int a,int b)
	    {
	        int a_rep=find(a),b_rep=find(b);
	        if(a_rep==b_rep)
	        return;
	        if(rank[a_rep]<rank[b_rep])
	        par[a_rep]=b_rep;
	        else if(rank[a_rep]>rank[b_rep])
	        par[b_rep]=a_rep;
	        else
	        {
	            par[b_rep]=a_rep;
	            rank[a_rep]++;
	        }
	    }
	}

	//SEGMENT TREE CODE

	// public static void segmentUpdate(int si,int ss,int se,int qs,int qe,long x)
	// {
	// 	if(ss>qe || se<qs)return;
	// 	if(qs<=ss && qe>=se)
	// 	{
	// 		seg[si][0]+=1L;
	// 		seg[si][1]+=x*x;
	// 		seg[si][2]+=2*x;
	// 		return;
	// 	}
	// 	int mid=(ss+se)/2;
	// 	segmentUpdate(2*si+1,ss,mid,qs,qe,x);
	// 	segmentUpdate(2*si+2,mid+1,se,qs,qe,x);
	// }
	// public static long segmentGet(int si,int ss,int se,int x,long f,long s,long t,long a[])
	// {
	// 	if(ss==se && ss==x)
	// 	{
	// 		f+=seg[si][0];
	// 		s+=seg[si][1];
	// 		t+=seg[si][2];
	// 		long ans=a[x]+(f*((long)x+1L)*((long)x+1L))+s+(t*((long)x+1L));
	// 		return ans;
	// 	}
	// 	int mid=(ss+se)/2;
	// 	if(x>mid){
	// 		return segmentGet(2*si+2,mid+1,se,x,f+seg[si][0],s+seg[si][1],t+seg[si][2],a);
	// 	}else{
	// 		return segmentGet(2*si+1,ss,mid,x,f+seg[si][0],s+seg[si][1],t+seg[si][2],a);
	// 	}
	// }

	public static class pair
    {
    	int a;
    	int b;
    	public pair(int val,int index)
    	{
    	    a=val;
    	    b=index;
    	}
    }
	public static class myComp implements Comparator<pair>
	{
		//sort in ascending order.
		public int compare(pair p1,pair p2)
		{
			if(p1.a==p2.a)
    	    return 0;
    	    else if(p1.a<p2.a)
    	    return -1;
    	    else
    	    return 1;
		}
		//sort in descending order.
		// public int compare(pair p1,pair p2)
    	// {
    	//     if(p1.a==p2.a)
    	//     return 0;
    	//     else if(p1.a<p2.a)
    	//     return 1;
    	//     else
    	//     return -1;
    	// }
	}
    public static class myComp1 implements Comparator<pair1>
    {
		//sort in ascending order.
    	public int compare(pair1 p1,pair1 p2)
    	{
    	    if(p1.a==p2.a)
    	    return 0;
    	    else if(p1.a<p2.a)
    	    return -1;
    	    else
    	    return 1;
    	}
		//sort in descending order.
		// public int compare(pair p1,pair p2)
    	// {
    	//     if(p1.a==p2.a)
    	//     return 0;
    	//     else if(p1.a<p2.a)
    	//     return 1;
    	//     else
    	//     return -1;
    	// }
    }
	public static class pair1
    {
    	long a;
    	long b;
    	public pair1(long val,long index)
    	{
    	    a=val;
    	    b=index;
    	}
    }
    public static ArrayList<pair1> mergeIntervals(ArrayList<pair1> arr)
	{
	    //****************use this in main function-Collections.sort(arr,new myComp1());
	    ArrayList<pair1> a1=new ArrayList<>();
	    if(arr.size()<=1)
	    return arr;
	    a1.add(arr.get(0));
	    int i=1,j=0;
	    while(i<arr.size())
	    {
	        if(a1.get(j).b<arr.get(i).a)
	        {
	           a1.add(arr.get(i));
	           i++;
	           j++;
	        }
	        else if(a1.get(j).b>arr.get(i).a && a1.get(j).b>=arr.get(i).b)
	        {
	            i++;
	        }
	        else if(a1.get(j).b>=arr.get(i).a)
	        {
	            long a=a1.get(j).a;
	            long b=arr.get(i).b;
	            a1.remove(j);
	            a1.add(new pair1(a,b));
	            i++;
	        }
	    }
	    return a1;
	}
	public static boolean palindrome(String s,int n)
	{
		for(int i=0;i<=n/2;i++){
			if(s.charAt(i)!=s.charAt(n-i-1)){
				return false;
			}
		}
		return true;
	}
	public static long countDigit(long n)
	{
	    long sum=0;
	    while(n!=0)
	    {
	        sum++;
	        n=n/10;
	    }
	    return sum;
	}
	public static long digitSum(long n)
	{
	    long sum=0;
	    while(n!=0)
	    {
	        sum=sum+n%10;
	        n=n/10;
	    }
	    return sum;
	}
	public static long gcd(long a,long b)
	{
	    if(b==0)
	    return a;
	    else
	    return gcd(b,a%b);
	}
	public static int gcd(int a,int b)
	{
	    if(b==0)
	    return a;
	    else
	    return gcd(b,a%b);
	}
	public static long pwr(long m,long n)
	{
		long res=1;
		m=m%mod;
		if(m==0)
		return 0;
		while(n>0)
		{
			if((n&1)!=0)
			{
				res=(res*m)%mod;
			}
			n=n>>1;
			m=(m*m)%mod;
		}
		return res;
	}
	public static void sort(int[] A)
	{
        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i)
		{
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
    }
    public static void sort(long[] A)
	{
	    int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i)
		{
            long tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
	    Arrays.sort(A);
	}
    public static int I()throws IOException{return sc.nextInt();}
    public static long L()throws IOException{return sc.nextLong();}
    public static String S()throws IOException{return sc.readLine();}
    public static double D()throws IOException{return sc.nextDouble();}
}
class FastReader {
	final private int BUFFER_SIZE = 1 << 16;
	private DataInputStream din;
	private byte[] buffer;
	private int bufferPointer, bytesRead;

	public FastReader()
	{
		din = new DataInputStream(System.in);
		buffer = new byte[BUFFER_SIZE];
		bufferPointer = bytesRead = 0;
	}

	public FastReader(String file_name) throws IOException
	{
		din = new DataInputStream(
			new FileInputStream(file_name));
		buffer = new byte[BUFFER_SIZE];
		bufferPointer = bytesRead = 0;
	}

	public String readLine() throws IOException
	{
		byte[] buf = new byte[64]; // line length
		int cnt = 0, c;
		while ((c = read()) != -1) {
			if (c == '\n') {
				if (cnt != 0) {
					break;
				}
				else {
					continue;
				}
			}
			buf[cnt++] = (byte)c;
		}
		return new String(buf, 0, cnt);
	}

	public int nextInt() throws IOException
	{
		int ret = 0;
		byte c = read();
		while (c <= ' ') {
			c = read();
		}
		boolean neg = (c == '-');
		if (neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');

		if (neg)
			return -ret;
		return ret;
	}

	public long nextLong() throws IOException
	{
		long ret = 0;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');
		if (neg)
			return -ret;
		return ret;
	}

	public double nextDouble() throws IOException
	{
		double ret = 0, div = 1;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();

		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');

		if (c == '.') {
			while ((c = read()) >= '0' && c <= '9') {
				ret += (c - '0') / (div *= 10);
			}
		}

		if (neg)
			return -ret;
		return ret;
	}

	private void fillBuffer() throws IOException
	{
		bytesRead = din.read(buffer, bufferPointer = 0,
							 BUFFER_SIZE);
		if (bytesRead == -1)
			buffer[0] = -1;
	}

	private byte read() throws IOException
	{
		if (bufferPointer == bytesRead)
			fillBuffer();
		return buffer[bufferPointer++];
	}

	public void close() throws IOException
	{
		if (din == null)
			return;
		din.close();
	}
}