There are $$$N$$$ witch huts each with a witch in it. One of these witches is evil. You want to find which witch hut has the evil witch.
To do this, you assign other players to check these witch huts. You start with $$$K$$$ (an initial value you choose) players. You can assign each player to investigate any amount of witch huts. They all disperse and take $$$C$$$ time to check the assigned witch huts and come back to you at the same time.
When the players come back to you, they either have the "Bad Luck" effect on them if they checked the evil witch hut or they have "Good Luck" effect on them if they did NOT visit the evil witch hut. The players that checked the evil witch don't know which one of the witch huts they visited gave them the "Bad Luck" effect though (the "Bad Luck" effect is the only indicator). Additionally, because the players with the "Bad Luck" effect have bad luck, one of them is chosen at random and permanently dies, meaning they can't help with the witch hut checking anymore. If no players come back with the "Bad Luck" effect, no players die.
You want to find the evil witch within $$$T$$$ time, but not very many players are willing to help out. What's the minimum number of players $$$K$$$ you need to start with to guarantee finding the evil witch?
Each test case consists of only 3 numbers $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$), $$$C$$$ ($$$1 \leq C \leq 10^5$$$), and $$$T$$$ ($$$1 \leq T \leq 10^5$$$).
Print only $$$K$$$, the minimum number of players you need to start with to guarantee finding the evil witch. If no amount of players can guarantee finding the evil witch, output $$$-1$$$.
3 15 15
2
10 10 23
2
6 26 20
-1
For the first test case, you can send player 1 to check hut 1 and player 2 to check hut 2 at time 0. If either of them comes back "Bad Luck" at $$$t=15$$$, you know that hut is evil. If neither come back with "Bad Luck", you know witch hut 3 is evil.
For the second test case, you can send player 1 to check witch huts 1, 2, 3, and 4 and player 2 to check huts 1, 2, 5, 6 at time 0.
At $$$t=10$$$:
1. If only player 1 comes back with "Bad Luck", you check witch huts 3 and 4 with player 2.
2. If only player 2 comes back with "Bad Luck", you check witch huts 5 and 6 with player 1.
3. If both come back with "Bad Luck", you check witch huts 1 and 2 with one of the players.
4. If neither come back with "Bad Luck", you check witch huts 7, 8, 9, 10 with both players.
At $$$t=20$$$, you will know which witch hut is the evil one.
For the third test case, you cannot determine the evil witch hut. Thus, you return "$$$-1$$$".
