409976: GYM103886 C Dice Game

Envy plays a game where he repeatedly rolls a standard six-sided die $$$n$$$ times in a row. On each roll he writes down the number he rolls.

When he is done, he multiplies all these numbers together to get $$$k$$$.

Unfortunately, Envy ate way too much cereal after he played the game, and took a long nap.

Now, he has forgotten what numbers he rolled!

Given $$$n$$$ and $$$k$$$, find the maximum possible sum of the numbers he rolled.

You are given $$$t$$$ independent test cases ($$$1 \leq t \leq 10$$$).

The first line of input will contain a single integer $$$t$$$.

For each test case, you are given two space separated integers, $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 5000$$$), ($$$1 \leq k \leq 10^6$$$)

For every test, print the maximum possible sum of all the numbers Envy rolled.

If there is no possible sequence of die rolls that satisfies $$$n$$$ and $$$k$$$, output -1.

5
6 84
5 12
6 64
5 100
6 33

-1
11
15
16
-1

For the first test case, no possible answer exists. For the second test case, one possible sequence of dice rolls to make the maximum sum is as follows: $$$1 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 6 \rightarrow 1$$$.

There are a total of $$$5$$$ numbers, which satisfies $$$n$$$, and a product of $$$12$$$, which satisfies $$$k$$$. It can be proved that $$$1 + 1 + 2 + 1 + 6 + 1 = 11$$$ is the maximal sum.