You are given a number X and K. Break X into K parts x₁, x₂, x₃ ... x_k such that the product of parts is X and sum is maximum possible. where (x _i > 1 and is Integer).

INPUT

The first line will contain t number of test cases.

Next t lines will contain two numbers X and K.

OUTPUT

For each testcase print single integer as a sum of all the parts.

CONSTRAINTS

1 <= t <= 10

1 <= X <= 10⁵

1 <= K <= 10