Bạn có muốn là số 1?

M vừa nhận giải nhất trong cuộc thi học sinh giỏi Tin học. Khi được nhà báo hỏi về cảm xúc của mình khi đứng ở vị trí số 1, M nói rằng: "Trước khi bắt đầu một cuộc thi, em không nghĩ mình sẽ là số 1, em chỉ cố gắng quyết tâm cao nhất có thể, vì Tin học là đam mê của em. Em cũng không có ý nghĩ mình sẽ là số 1 mãi mãi, nhưng em sẽ luôn quyết tâm cao nhất cho những đam mê của mình. Ngay bây giờ, em muốn tiếp tục rèn luyện, rèn luyện, và rèn luyện." Sau này, M trở thành một doanh nhân thành đạt trong lĩnh vực công nghệ thông tin. Trong những năm tháng học dưới mái trường Lê, M có những lần đạt vị trí số 1, có những lần không, nhưng M luôn học với quyết tâm cao nhất, và rất khiêm tốn. Để nói về tinh thần của M cho thế hệ sau, thầy giáo ra một bài toán như sau:

Cho 3 số nguyên n, k, m.

Xâu nhị phân là xâu chỉ gồm các kí tự 0, 1

Xâu nhị phân gọi là đẹp nếu nó gồm có k số 1

Các xâu đẹp được sắp xếp theo thứ tự từ điển, và đánh số từ 1, 2, ……

Nhiệm vụ của bạn là tìm xâu đẹp thứ m theo thứ tự từ điển. Nếu không có xâu như vậy thỏa mãn, hãy đưa ra -1

Input

Dòng đầu tiên gồm số nguyên T, biểu thị số test

T dòng tiếp tiếp theo, mỗi dòng gồm 3 số nguyên phân biệt là N, K, và M

Ouput

Ứng với mỗi test, đưa câu trả lời trên một dòng

Giới hạn:

1<=T<=10

1<=N<=350

1<=K<=N

M có tối đa 91 chữ số

Ví dụ:

Giải thích:

Trong test số 1. Các xâu đẹp (chiều dài N=3, số lượng số 1 là K=2, ta cần tìm xâu đẹp có thứ tự là K=2) là 011, 101, và 110. Do đó, xâu đẹp ở vị trí thứ 2 chính là 101