Mr. Seth decorates his shop with Paintings. He then planned to buy exactly K ones. He can buy them from a nearby shop and there are 2 types of Paintings available. The shop has a rule for customers that If anyone buys K paintings of type 1 then the customer must pay L * K² and L1 *M² if you buy M paintings of type 2. Please help Mr. Seth to buy exactly K paintings at a minimum amount of payment.

Input Format

The first line contains an integer T denoting the number of test cases.
Each test case is described in a single line containing three space-separated integers K, L, L1.

Output Format

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

Constraints

1 ≤ T ≤ 10⁵
1 ≤ K, L, L1 ≤ 10⁵