Division solution codechef

Division solution codechef

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 

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

Sample Output 1  Division solution codechef 



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.

Leave a Comment

Your email address will not be published.