cnr_16188
Chef has a special affection for sets of binary strings of equal length which have same numbers of 1's. Given three integers n, k and m, your task is to find the the lexicographically  m^th smallest string among strings  which have length n and have k 1's. If no such string exists output -1. 

Tips: 
 To see what lexicographic order means . See http://en.wikipedia.org/wiki/Lexicographical_order

Input
Input description.

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
The first and only line of each test case contains three space separated integers N ,  K  and  M 


Output
For each test case output the answer on a separate line .

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 350
1 ≤ K ≤ N


Example
Input:
1
3 2 2

Output:
101

Explanation
Example case 1. The set of strings in lexicographic order is "011", "101", and "110" 

 Scoring 
Subtask 1 (41 point):

1 ≤ N ≤ 20

Subtask 2 (59 points):

1 ≤ N ≤ 350
from math import *

def nCr(n, k):
	if ((k>n) or (k<0)):
		return 0
	if (k==0):
		return 1
	if (k==1):
		return n
	if (k==n):
		return 1
	return factorial(n)/(factorial(n-k)*factorial(k))

def solve(m, n, k):
	global ans
	if (n==0):
		return
	check = nCr(n-1, k)
	if (m <= check):
		ans += '0'
		solve(m, n-1, k)
	else:
		ans += '1'
		solve(m-check, n-1, k-1)

t = int(raw_input())
for i in range(t):
    n, k, m = list(map(int, raw_input().split(" ")))
    ans = ""
    if (nCr(n, k) >= m):
    	solve(m, n, k)
    	print (ans)
    else:
    	print ('-1')