• # For Solution

Chef has an integer NN. He repeats the following operation until NN becomes 11.

• Chef chooses an integer XX such that X>1X>1 and XX is a divisor of NN and then divides NN by XX (the new value of NN becomes N/XN/X). If XX is even, Chef gets AA points otherwise he gets BB points

Can you find the maximum points Chef can get if he performs the operations optimally?

### Input Format Division solution codechef

• First line will contain TT, number of testcases. Then the testcases follow.
• Each testcase contains of a single line of input containing three integers N,A,BN,A,B.

### Output Format Division solution codechef

For each testcase, output in a single line the maximum points Chef can get.

### Constraints Division solution codechef

• 1T21031≤T≤2⋅103
• 2N1092≤N≤109
• 103A,B103−103≤A,B≤103

### Sample Input 1  Division solution codechef

4
10 2 3
15 5 -2
12 2 3
8 -1 0


### Sample Output 1  Division solution codechef

5
-2
7
-1


### Explanation

Test case 11: First Chef divides N=10N=10 by 22 and gets 22 points and then divides by 55 and thus gets 33 points. Hence Chef gets a total of 2+3=52+3=5 points.

Test case 22: Chef divides NN by 1515. Hence he gets 2−2 points.