Special Shop
Tag(s):

## Algorithms, Searching, differentiation

Problem
Editorial
Analytics

Creatnx now wants to decorate his house by flower pots. He plans to buy exactly $N$ ones. He can only buy them from Triracle's shop. There are only two kind of flower pots available in that shop. The shop is very strange. If you buy $X$ flower pots of kind 1 then you must pay $A\times X^2$ and $B\times Y^2$ if you buy $Y$ flower pots of kind 2. Please help Creatnx buys exactly $N$ flower pots that minimizes money he pays.

Input Format

The first line contains a integer $T$ denoting the number of test cases.

Each of test case is described in a single line containing three space-separated integers $N, A, B$.

Output Format

For each test case, print a single line containing the answer.

Constraints

• $1\le T \le 10^5$
• $1\le N, A, B \le 10^5$

SAMPLE INPUT
2
5 1 2
10 2 4


SAMPLE OUTPUT
17
134

Explanation

Query 1: we have to buy exactly $5$ pots. There are six possible options:

• Buy $0$ pot of first kind, $5$ pots of second kind. The cost is: $1\times 0^2 + 2\times 5^2 = 50$.
• Buy $1$ pot of first kind, $4$ pots of second kind. The cost is: $1\times 1^2 + 2\times 4^2 = 33$.
• Buy $2$ pots of first kind, $3$ pots of second kind. The cost is: $1\times 2^2 + 2\times 3^2 = 22$.
• Buy $3$ pots of first kind, $2$ pots of second kind. The cost is: $1\times 3^2 + 2\times 2^2 = 17$.
• Buy $4$ pots of first kind, $1$ pot of second kind. The cost is: $1\times 4^2 + 2\times 1^2 = 18$.
• Buy $5$ pots of first kind, $0$ pot of second kind. The cost is: $1\times 5^2 + 2\times 0^2 = 25$.

So, the optimal cost is $17$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

July Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Geometry
• Algorithms > Graphs
• Math > Number Theory
• Algorithms > Searching