Intensive Training

To prepare for the upcoming ICPC Regional Contest, you decided to train intensively for the next $N$ days (numbered from $1$ to $N$). During the intensive training, you want to solve problems from the training platform INCOJ. In INCOJ, each problem has a difficulty rating, which is a non-negative integer. For each rating, there are $10^{100}$ problems that you can pick to solve.

You want to plan a schedule for your intensive training. On day $i$, you plan to solve exactly $k_i$ problems, each with difficulty rating $r_i$, where $k_i$ and $r_i$ are non-negative integers. On a single day, you may solve $0$ problems with a non-zero rating, which means you do not solve any problems that day. You may also solve multiple problems with difficulty $0$, since those problems are too easy for you.

Your schedule must follow these constraints.

• To focus on quality over quantity, the number of problems on each day cannot exceed the previous day's count, and the difficulty rating cannot be less than the previous day's rating. Formally, $k_{i-1} \ge k_i$ and $r_{i-1} \le r_i$ for $2 \le i \le N$.
• To avoid burning out, the total number of problems must be exactly $K$, and the sum of difficulty ratings across all days must be exactly $R$. Formally, $k_1 + k_2 + \cdots + k_N = K$ and $r_1 + r_2 + \cdots + r_N = R$.

The productivity of a day is the number of problems solved that day multiplied by their difficulty rating, that is, $k_i \times r_i$. Find the maximum total productivity across all $N$ days.

This is a multi-case problem. The first line contains an integer $T$ ($1 \le T \le 100$), the number of test cases.

Each test case consists of one line with three integers $N$, $R$, and $K$ ($1 \le N, R, K \le 10^9$).

For each test case, print the maximum total productivity on a single line as an integer.