kth_char_string.cpp

using namespace std;
#include <bits/stdc++.h>
#define trace(x) cout<<#x<<": "<<x<<" ";

int solve(string s, int n, int k)
{
	if(n == 0)
		return s[k];

	int skip = k/((int)pow(2, n));
	k = k%((int)pow(2, n));
	
	if(s[skip] == '0')
		s = "01";
	else 
		s = "10";

	return solve(s, n-1, k);
}






int main(int argc, char const *argv[])
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m,k;
		cin>>m>>k>>n;

		string s;

		while(m)
		{
			if(m%2)
				s += '1';
			else s += '0';
			m /= 2;
		}

		string s1;
		for (int i = s.size()-1; i >= 0; i--) 
		{
			s1 += s[i];
		}

		cout<<(char)solve(s1, n, k)<<endl;





	}
	return 0;
}