Kuo Double-Junior is obsessed with "Grassy-Muddy Horse", a kind of toys manufactured by the factory "Swinging Grass". It is said that every "Grassy-Muddy Horse" manufactured has a unique binary ID (consists of solely '0' and '1') of fixed length L. Further more, since the boss of "Swinging Grass" hates the digit zero (it's not prime, not really composite either, what the heck?) so each binary ID does not contain consecutive zeroes of length more than Z (a fixed number). The "Grassy Muddy Horses" are manufactured in the order according to their ID's lexicographical order, increasingly.
Kuo wants to buy a "Grassy Muddy Horse", but he has a lucky number, k. Therefore Kuo wants to acquire the k-th "Grassy Muddy Horse" manufactured. However he fails to do so after a period of struggling with zeroes and ones. Please help him find the answer.
The first line contain an integer T --- the number of tests(1<=T<=1000).
Each test contains three integers L,Z,k as the problem description(1<=L<=100, 0<=Z<=100, 1<=k<=2,147,483,647).
3 5 2 1 5 2 2 5 2 32
00100 00101 No Solution
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|