Lissa has just won the HackerEarth Online Coding Contest. Kuldeep decided to offer her N chocolate boxes each containing at least one chocolate in it. But he knows that Lissa does not like chocolates very much so he wants to place chocolates in the boxes such that the total number of chocolates is minimum.

Given a number N denoting the number of boxes and a number K denoting the product of the number of chocolates in the N boxes, you need to tell Kuldeep the minimum of total number of chocolates that can be placed in the boxes.

Input:

First line of input contains an integer T denoting the total number of test cases.

Each test case consists of a single line containing two space separated integers N and K denoting the number of boxes and the product of the chocolates in n boxes.

Output:

Output consists of T lines each containing an integer denoting the minimum of total number of chocolates in the N boxes.

Constraints:

\( T \le 1000\)

\(N \le 1000\)

\(K \le 10^9\)