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 CPP):

Solution:
#include<bits/stdc++.h>
#define ll long long int
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define inf (1<<30)
#define linf 1e18
#define ninf -1e9
#define loop(i,r) for(int i = 0; i < (r) ; i++)
#define loop1(i,r) for(int i=1;i<=r;i++)
#define looplr(i,l,r) for(int i=l;i<=r;i++)
#define rloop(i,r) for(int i=r;i>=0;i--)
#define min3(x1, x2, x3) (x3 > min(x1, x2) ? min(x2, x1) : x3)
#define max3(x1, x2, x3) (x3 < max(x1, x2) ? max(x1, x2) : x3)
#define sz(a) int((a).size())
#define vi vector< int >
#define vl vector<long long int>
#define vpi vector<pair<int, int> >
#define vpl vector<pair<long long int, long long int> >
#define pb push_back
#define umi unordered_map<int , int>
#define umc unordered_map<char , int>
#define uml unordered_map<long long int , long long int>
#define mpi map<int, int>
#define mpl map<ll, ll>
#define sti set<int>
#define stl set<long long int>
#define ff first
#define ss second
#define len(x) (int)x.length()
#define ctn continue
#define brk break
#define ub(i,x) upper_bound(i.begin(), i.end(),x)
#define lb(i,x) lower_bound(i.begin(), i.end(),x)
#define ump unordered_map
#define str string
#define pll pair<long long int, long long int>
#define pii pair<int, int>
#define memn1(x) memset(x,-1,sizeof(x))
#define mem1(x) memset(x,1,sizeof(x))
#define mem0(x) memset(x,0,sizeof(x))
#define rtn return
#define srt(x) sort(all(x))
#define srtgi(x) sort(all(x), greater<int>())
#define srtgl(x) sort(all(x), greater<ll>())
#define srtgpi(x) sort(all(x), greater<pii>())
#define srtgpl(x) sort(all(x), greater<pll>())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define nline cout<< "\n"
#define chngl "\n"
#define takei(input) scanf("%d",&input)
#define takel(input) scanf("%lld",&input)
#define takepl(input1,input2) scanf("%lld %lld",&input1, &input2)
#define takepi(input1, input2) scanf("%d %d",&input1, &input2)
#define PI (acos(-1))
#define mxpqi priority_queue<int>
#define mnpqi priority_queue<int, vector<int>, greater<int>>
#define mxpql priority_queue<ll>
#define mnpql priority_queue<ll, vector<ll>, greater<ll>>
#define putyes printf("Yes\n")
#define putno printf("No\n")

const int  mod = 1e9 + 7;
int dx[] = {0, 0, 1, -1};
int dy[] = { -1, 1, 0, 0};

using namespace std;
// #include<boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
//cpp_int

int getDigit ( int num ) {
	unsigned digit = 0 ;
	while ( num != 0 ) {
		num /= 10 ;
		digit ++;
	}
	return digit ;
}

ll Fact ( ll k ) {
	ll sum = 1 ;
	for ( ll i = 1 ; i <= k ; ++ i )
	{
		sum *= i ;
	}
	return sum ;
}
bool prime_checker(ll x) {
	for (ll i = 2; i * i <= x; i++) {
		if (x % i == 0) rtn false;
	}
	rtn true;
}
// Prime factor decomposition ex: {{2, 2}, {5, 1}, {101, 1}}
map<ll, ll> prime_fact(ll N) {
	map<ll, ll> res;
	for (ll a = 2; a * a <= N; ++a) {
		if (N % a != 0) continue;
		ll ex = 0 ; // exponent
		// Keep splitting as long as it breaks
		while (N % a == 0) {
			++ex;
			N /= a;
		}
		// push the result
		res[a] = ex;
	}
	// About the last remaining number
	if (N != 1) res[N] = 1;
	return res;
}

ll modPow(long long a, long long n,  long p) {
	if ( n == 0 ) return 1 ; // When supporting 0th power
	if (n == 1) return a % p;
	if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
	long long t = modPow(a, n / 2, p);
	return (t * t) % p;
}
//----------------------P&C-------------------------------------
ll f [ 2000001 ], rf [ 2000001 ];
ll inv (ll x) {
	ll res = 1 ;
	ll k = mod - 2 ;
	ll y = x;
	while (k) {
		if (k & 1 ) res = (res * y) % mod;
		y = (y * y) % mod;
		k /= 2 ;
	}
	return res;
}

ll C ( int n, int k) {
	if (k == 0 || n == k) rtn 1;
	if (k < 0 || n < k) return  0 ;
	////Init
	f [ 0 ] = 1 ;
	loop1 (i, n ) f [i] = (f [i - 1 ] * i) % mod;
	rf [ n - 1 ] = inv (f [ n - 1 ]);
	rloop (i, n - 2) rf [i] = (rf [i + 1 ] * (i + 1 )) % mod;
	/////end

	ll a = f [n]; // = n!
	ll b = rf [n - k]; // = (n-k)!
	ll c = rf [k]; // = k!

	ll bc = (b * c) % mod;

	return (a * bc) % mod;
}
ll P ( int n, int k) {
	if (k < 0 || n < k) return  0 ;

	ll a = f [n]; // = n!
	ll b = rf [n - k]; // = (n-k)!
	return (a * b) % mod;
}
ll H ( int n, int k) {
	if (n == 0 && k == 0 ) return  1 ;
	return C (n + k - 1 , k);
}
//----------------------------P&C-------------------------------------------

//-----------------runLengthEncoding--------------------------------
vector<pair<char, int>> RLE(string s) {
	int n = s.length();

	vector<pair<char, int>> res;
	char pre = s[0];
	int cnt = 1;
	for (int i = 1; i < n; i++) {
		if (pre != s[i]) {
			res.push_back({ s[i - 1], cnt });
			pre = s[i];
			cnt = 1;
		}
		else cnt++;
	}

	res.push_back({ pre, cnt });
	//for (auto &i : res) cout << i.ss << ' ' << i.ff << endl;
	return res;
}
//------------------------------------------------------------------

const int NN = 1e6 + 5;
int Prime[NN];
vector<int> prime;
void calPrime() {
	for (int i = 1; i <= 1000000; i++) Prime[i] = 1;
	for (int i = 2; i * i <= 1e6 + 1; i++) {
		if (Prime[i] == -1) ctn;
		Prime[i] = 1;
		prime.pb(i);
		for (int j = 2 * i; j <= 1e6 + 1; j +=  i) {
			Prime[j] = -1;
		}
	}

}
//----------------------max & min--------------------------------
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
//----------------------DSU------------------------------------------
int getparent(int a, vi &parent) {
	if (parent[a] == a) return a;
	return parent[a] = getparent(parent[a], parent);
}
void Union(int a, int b, vi &parent, vi &rank) {
	int pa = getparent(a, parent);
	int pb = getparent(b, parent);
	if (rank[pa] == rank[pb]) rank[pa]++;
	if (rank[pa] >= rank[pb]) {
		parent[pb] = pa;
	} else {
		parent[pa] = pb;
	}
}

//---------------------Count number of prime fact------------------
ll cntprime(int x)
{
	int res = 0, i;
	for (i = 2; i * i <= x; i++)
	{
		while (x % i == 0)
		{
			x /= i;
			res++;
		}
	}
	if (x > 1) res++;
	return res;
}

//-------------------------SPF-----------------------------------------
#define MAXN   1000001
int spf[MAXN];

void sieve()
{
	spf[1] = 1;
	for (int i = 2; i < MAXN; i++) spf[i] = i;
	for (int i = 4; i < MAXN; i += 2) spf[i] = 2;

	for (int i = 3; i * i < MAXN; i++)
	{
		if (spf[i] == i)
		{
			for (int j = i * i; j < MAXN; j += i)
				if (spf[j] == j)
					spf[j] = i;
		}
	}
}

// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization(int x)
{
	vector<int> ret;
	while (x != 1)
	{
		ret.push_back(spf[x]);
		x = x / spf[x];
	}
	return ret;
}
//---------------------------------------------------------------------------
//int getDigit ( int num )
// ll Fact ( ll k ) O(k)
// vector<pair<ll, ll> > prime_fact(ll N)
//bool prime_checker(x)
//ll cntprime(ll x)
//ll modPow(ll a, ll n,  ll p)


void solve() {
	ll n, k; cin >> n >> k;
	vl v(n + 6);
	ll cnt = 2, check = 3;
	v[0] = 0, v[1] = 1, v[2] = 3, v[3] = 1;
	loop(i, n) {
		if (i <= 3) {
			cout << v[i] ;
			nline;
		}
		else {
			ll temp = i;
			while ((temp % 2) == 0) temp /= 2;
			if (temp == 1) {
				cnt *= 2;
				check += cnt;
				v[i] = check;
				cout << check;
				nline;
			}
			else {
				v[i] = v[i - cnt];
				cout << v[i] ;
				nline;
			}
		}
		cout.flush();
		ll inpt; cin >> inpt;
		if (inpt == 1) brk;
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//calPrime();
	int tme = 1;
	cin >> tme;

	while (tme--) {
		//cout << "Case #" << i << ": ";
		solve();

		//i++;
	}
	return 0;
}