<p align="justify">Let's 
consider the 32 bit representation of all integers i from m up to n 
inclusive (m ≤ i ≤ n; m × n ≥ 0, -2^31 ≤ m ≤ n ≤ 2^31-1). Note that a 
negative number is represented in 32 bit Additional Code. That is the 32 bit 
sequence, the binary sum of which and the 32 bit representation of the 
corresponding positive number is 2^32 (<tt>1 
0000 0000 0000 0000 0000 0000 0000 0000</tt> 
in binary). </p>
<p align="justify">For 
example, the 32 bit representation of 6 is <tt>
0000 0000 0000 0000 0000 0000 0000 0110</tt>
</p>
<p align="justify">
and 
the 32 bit representation of -6 is <tt>1111 1111 
1111 1111 1111 1111 1111 1010</tt>
</p>
<p align="justify">
because</p>
<p align="justify">
<tt>   
0000 0000 0000 0000 0000 0000 0000 0110</tt> 
(6) <br>
+ <br>
<tt>   
1111 1111 1111 1111 1111 1111 1111 1010</tt> 
(-6) <br>	
-------------------------------------------------<br>
<tt>= 1 0000 0000 0000 0000 0000 0000 0000 0000</tt> 
(2^32) </p>
<p align="justify">Let's 
sort the 32 bit representations of these numbers in increasing order of the 
number of bit 1. If two 32 bit representations that have the same number of 
bit 1, they are sorted in lexicographical order. </p>
<p align="justify">For 
example, with m = 0 and n = 5, the result of the sorting will be 
</p>
<table border="1" cellspacing="0" cellpadding="0">
	<tbody><tr>
		<td width="10%">
		<p align="justify">
		No.</p></td>
		<td width="26%">
		<p align="justify">
		Decimal number</p></td>
		<td width="63%">
		<p align="justify">
		Binary 32 bit representation</p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		1</p></td>
		<td width="26%">
		<p align="justify">
		0</p></td>
		<td width="63%">
		<p align="justify"><tt>
		0000 0000 0000 0000 0000 0000 0000 0000</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		2</p></td>
		<td width="26%">
		<p align="justify">
		1</p></td>
		<td width="63%">
		<p align="justify"><tt>
		0000 0000 0000 0000 0000 0000 0000 0001</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		3</p></td>
		<td width="26%">
		<p align="justify">
		2</p></td>
		<td width="63%">
		<p align="justify"><tt>
		0000 0000 0000 0000 0000 0000 0000 0010</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		4</p></td>
		<td width="26%">
		<p align="justify">
		4</p></td>
		<td width="63%">
		<p align="justify"><tt>
		0000 0000 0000 0000 0000 0000 0000 0100</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		5</p></td>
		<td width="26%">
		<p align="justify">
		3</p></td>
		<td width="63%">
		<p align="justify"><tt>
		0000 0000 0000 0000 0000 0000 0000 0011</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		6</p></td>
		<td width="26%">
		<p align="justify">
		5</p></td>
		<td width="63%">
		<p align="justify"><tt>
		0000 0000 0000 0000 0000 0000 0000 0101</tt></p></td>
	</tr>
</tbody></table>
<p align="justify">
with 
m = -5 and n = -2, the result of the sorting will be </p>
<table border="1" cellspacing="0" cellpadding="0">
	<tbody><tr>
		<td width="10%">
		<p align="justify">
		No.</p></td>
		<td width="26%">
		<p align="justify">
		Decimal number</p></td>
		<td width="63%">
		<p align="justify">
		Binary 32 bit representation</p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		1</p></td>
		<td width="26%">
		<p align="justify">
		-4</p></td>
		<td width="63%">
		<p align="justify"><tt>
		1111 1111 1111 1111 1111 1111 1111 1100</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		2</p></td>
		<td width="26%">
		<p align="justify">
		-5</p></td>
		<td width="63%">
		<p align="justify"><tt>
		1111 1111 1111 1111 1111 1111 1111 1011</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		3</p></td>
		<td width="26%">
		<p align="justify">
		-3</p></td>
		<td width="63%">
		<p align="justify"><tt>
		1111 1111 1111 1111 1111 1111 1111 1101</tt></p></td>
	</tr>
	<tr>
		<td width="10%">
		<p align="justify">
		4</p></td>
		<td width="26%">
		<p align="justify">
		-2</p></td>
		<td width="63%">
		<p align="justify"><tt>
		1111 1111 1111 1111 1111 1111 1111 1110</tt></p></td>
	</tr>
</tbody></table>
<p align="justify">
 </p>
<p align="justify">
Given m, n 
and k (1 ≤ k ≤ min{n − m + 1, 2 147 473 547}), 
your task is to write a program to find a number corresponding to k-th 
representation in the sorted sequence. </p>

<h3>Input</h3>
<p>
The input 
consists of several data sets. The first line of the input file contains the 
number of data sets which is a positive integer and is not bigger than 1000. 
The following lines describe the data sets. </p>
<p align="justify">
For each 
data set, the only line contains 3 integers m, n 
and k separated by space. </p>

<h3>Output</h3>
<p>
For each 
data set, write in one line the k-th number of the sorted numbers. 
</p>

<h3>Example</h3>

Sample input:
2
0 5 3
-5 -2 2
Sample output:
2
-5