407339: GYM102767 E Singhal and Numbers

Yestarday, Singhal went to a shop. The shop owner is a mathematician and has a unique style of costing the items costumer bought.

If a item has a initial price $$$X (X \ge 2)$$$ , then costumer can bought $$$N$$$ items of this price if $$$X\pmod N = 0$$$ and $$$ 1 \le N \le X-1$$$.

Example - If a item cost $$$X = 10$$$, then costumer can buy these $$$(1,2,5)$$$ numbers of items of this price.

If a item cost $$$X = 12$$$, then costumer can buy these $$$(1,2,3,4,6)$$$ numbers of items.

The shop owner will then calculates the total cost of $$$N$$$ items as -

1) if $$$N$$$ is Prime , cost will be $$$$$$ A + \frac{X}{N} $$$$$$

2) if $$$N$$$ is Composite , cost will be $$$$$$ B + \frac{X}{N} $$$$$$

3) if $$$N$$$ is $$$1$$$ , cost will be $$$$$$ C + \frac{X}{N} $$$$$$

Defn of Prime and Composite number - https://www.mathsisfun.com/prime-composite-number.html.

You know the value of $$$A,B,C$$$ and $$$X$$$. Help him to buy $$$N$$$ number of items of price $$$X$$$ so that cost will be minimum possible.

You don't have to minimize the number of items , only minimize the total cost.

The first line contains a single integer $$$t (1 \le t \le 10^5)$$$ — the number of test cases in the input. Then $$$t$$$ test cases follow.

Each query contains two lines. The first line contains a integer $$$X(2 \le X \le 10^7)$$$: Price of item , and the second line contains $$$A,B,C (1\le A,B,C \le 10^9)$$$.

Print $$$t$$$ answers to the test cases. Each answer must be consisting of single integer — the minimum possible cost.

3
12
2 5 1
12
2 3 1
12
15 15 1

6
5
13

In the first query, possible numbers of items he can buy is $$$(1,2,3,4,6)$$$.

Cost for each N is —

$$$ N = 1 - C + \frac{X}{N}$$$ $$$i.e.$$$ $$$1 + \frac{12}{1} = 13$$$

$$$ N = 2 - 2 + \frac{12}{2} = 8$$$

$$$ N = 3 - 2 + \frac{12}{3} = 6$$$

$$$ N = 4 - 5 + \frac{12}{4} = 8$$$

$$$ N = 6 - 5 + \frac{12}{6} = 7$$$

Minimum cost from this will be - $$$6$$$.

In the second query, possible numbers of items he can buy is $$$(1,2,3,4,6)$$$ and Cost for each N will be $$$(13,8,6,6,5)$$$ respectively.

In the third query, possible numbers of items he can buy is $$$(1,2,3,4,6)$$$ and Cost for each N will be $$$(13,21,19,18,17)$$$ respectively.