awaykened has been stocking up on eggnog all year for his 2016 New Year's Party. cheesecake, as mischievous as ever, managed to sneak into the cellar and added some peanuts to one of the bottles. awaykened wants his party to be allergy-free, so he is determined to find the bottle!

He has decided to find it through the following steps:

• Every day, he will invite his friends who are allergic to peanuts over for a dinner party.
• Before the party, he will prepare drinks for his friends. For each friend, he will make a mixture of some subset of the eggnog he has.
• If a friend drinks a mixture containing eggnog from the bottle spiked with peanuts, they will have an allergic reaction and find out that awaykened is just using them as a guinea pig. Disheartened, they will leave and never come back to any subsequent dinner parties.
• After some days have passed, awaykened should be able to single out the spiked bottle based on the allergic reactions that occurred.

Of course, awaykened wants to determine the bottle before his New Year's Party. But he's so disoriented after a semester of English that he doesn't remember which of his friends are allergic to peanuts, or even how long he has before the party begins! Of course, he wasn't keeping count of how many bottles he had stocked up either. As such, he has ~Q~ queries, each of which is either type 1 or type 2.

Type 1: if awaykened has ~N~ bottles of eggnog and ~F~ friends who are allergic to peanuts, what is the minimum number of days it will take in order to guarantee that he can determine the spiked bottle?

Type 2: if awaykened has ~N~ bottles of eggnog and there are only ~D~ days before the party, what's the minimum number of testers that he needs in order to guarantee that he can determine the spiked bottle in time?

Constraints

Subtask 1 [20%]

~1 \le Q \le 10~

~1 \le N, F, D \le 100~

Subtask 2 [80%]

~1 \le Q \le 10^5~

~1 \le N, F, D \le 10^6~

Input Specification

The first line of input will contain ~Q~, the number of queries.

The next ~Q~ lines will each contain a query. Type 1 queries will be of the form 1 N F, type 2 queries will be of the form 2 N D.

Output Specification

Output the answer to each query on a separate line.

Sample Input

3
1 3 2
2 2 1
1 5 1

Sample Output

1
1
4

Explanation for Sample Output

Query 1: awaykened can have friend 1 drink a mixture of bottles 1 and 3 and friend 2 drink from a mixture of bottles 2 and 3. If one of them has an allergic reaction, the bottle that only they drank from had peanuts in it. If both have an allergic reaction, the third bottle is the spiked bottle. Therefore, he only needs 1 day.

Query 2: awaykened only needs one tester. The tester will drink eggnog from one of the bottles. If he has an allergic reaction, the bottle he drank from is spiked. Vice versa, if he doesn't, the other bottle is the one with peanuts.

Query 3: With only one tester, the only option is to have him/her drink the eggnog from a different bottle every day for 4 days. If he/she does not respond to any of them, the remaining bottle is the one that contains peanuts.