URI Online Judge | 2225
# Penalization

**Timelimit: 1**

By Thalyson Nepomuceno, UECE Brazil

In the game Pomekon, one of the goals is to visit real places to get new items and experience. Fulyane does not like to leave the house, she made a program that simulates its location, providing false coordinates of her location to the game. She also made a romote control that allows to move with fake coordinates, pretending as if she were really walking, but without leaving home.

Searching forums, she found that for not to be banned from the game, she would have to move using only the real routes, but also found that he could move instantly from one place to another, without using real routes no more than **K** times per day, because if she to teleport more than **K** times, she could be banned from the game forever.

Fulyane always starts at the location identified by the index 1, and wants to visit the all locations, using the teleport no more than **K** times.

The input contains several instances. The first line of input contains an integer **T** indicating the number of instances. The first line in each instance contains three integers **N** (1 ≤ **N** ≤ 15), **M** (1 ≤ **M** ≤ **N ^{2}**) and K (0 ≤

For each instance, print the minimum amount of minutes that Julyane takes to visit all locations, using no more than **K** teleporters. If you can not visit all places, print -1.

Input Sample | Output Sample |

2 |
7 |