Maximum Value

Let $x_1, x_2, \dots, x_m$ be real numbers that, for some integers $a$ and $b$ with $a > 0$, satisfy the following conditions:

1. $-\dfrac{1}{\sqrt{a}} \le x_i \le \sqrt{a}$ for every $i$;
2. $x_1 + x_2 + \dots + x_m = b\sqrt{a}$.

Given an even positive integer $p$, write a program that finds the maximum possible value of $x_1^p + x_2^p + \dots + x_m^p$.

The first line contains the number of test cases $T$. Each test case consists of a single line containing $m$, $p$, $a$, and $b$ ($m \le 2000$, $p \le 12$, and $p$ is even).

Only inputs for which real numbers $x_1, x_2, \dots, x_m$ satisfying the conditions exist are given.

For each test case, print on its own line the maximum value of the expression, rounded to the nearest integer (rounded at the first digit after the decimal point).