In a parallel universe, The Joker is a very good guy !!! He wishes to save as many people as possible of city Gotham from the criminals. For this purpose he decides to take Ninja training .There are three types of training he can get.
TYPE 1- on any given day, the cost of training is equal to the day number. i.e, on day 1 he pays 1 unit, on day 2 he pays 2 units, on day 3 he pays 3 units so on.
TYPE 2- on any given day, the cost of training is equal to the square of that particular day number. i.e, on day 1 he pays 12 units, on day 2 he pays 22 units, on day 3 he pays 32 units so on.
TYPE 3- on any given day, the cost of training is equal to the cube of that particular day number. i.e, on day 1 he pays 13 units, on day 2 he pays 23 units, on day 3 he pays 33 units so on.
For D days of training, the total cost will be equal to the sum of the amount he paid each day.
Now you are given Q number of queries. Each query consists of two integers N and K. K is the type of training in which he enrolls. N is the amount of money he has. For each query, calculate the maximum number of days he can take training (of type K) with N units of money.
INPUT -
The first line of the input contains a single integer Q denoting the number of queries. Each of the next Q lines contains two space separated integers N and K. N is the amount of money he has and K denotes the type of Ninja training in which he enrolled.
OUTPUT -
For each query, calculate the maximum number of days of training he can afford and print the answer in a new line.
CONSTRAINTS -
1≤Q≤106
0≤N≤1018
1≤K≤3
In the sample input, there are 5 queries.
In the first query, N = 2 and K = 3. on day one he pays 13 units. Remaining amount is 2 - 1 = 1 units. For day 2 he has to pay 23 = 8 units. Therefore, he cannot afford day 2.Therefore, he takes training for only one day.
In the third query, N = 5 and K = 1 . On day one he pays 1 unit. On day 2 he pays 2 units. So, total cost for 2 days is 3 units. Remaining amount is 5 - 3 = 2. On day 3 he has to pay 3 units. But, he has only 2 units. Therefore, he can afford maximum of 2 days of Type 1 training.