집중 훈련

곧 있을 ICPC 지역 예선에 대비하여, 앞으로 $N$일 동안(1일부터 $N$일까지 번호가 매겨짐) 집중 훈련을 하기로 했습니다. 집중 훈련 중에는 INCOJ라는 연습 플랫폼의 문제를 풀고자 합니다. INCOJ의 각 문제에는 0 이상의 정수인 난이도가 있습니다. 난이도마다 풀 수 있는 문제가 $10^{100}$개씩 있습니다.

집중 훈련의 일정을 계획합니다. $i$일에는 난이도 $r_i$인 문제를 정확히 $k_i$개 풀 계획입니다. 여기서 $k_i$와 $r_i$는 0 이상의 정수입니다. 하루에 난이도가 0이 아닌 문제를 0개 풀 수 있는데, 이는 그날 문제를 풀지 않겠다는 뜻입니다. 난이도 0인 문제를 여러 개 푸는 것도 가능합니다. 너무 쉬운 문제이기 때문입니다.

일정은 다음 제약을 지켜야 합니다.

• 양보다 질을 중시하므로, 하루의 문제 수는 전날의 문제 수를 넘을 수 없고, 난이도는 전날의 난이도보다 낮을 수 없습니다. 형식으로 쓰면, $2 \le i \le N$인 모든 $i$에 대해 $k_{i-1} \ge k_i$이고 $r_{i-1} \le r_i$입니다.
• 번아웃을 피하기 위해, 푸는 문제의 총수는 정확히 $K$여야 하고, 모든 날의 난이도 합은 정확히 $R$이어야 합니다. 형식으로 쓰면, $k_1 + k_2 + \cdots + k_N = K$이고 $r_1 + r_2 + \cdots + r_N = R$입니다.

하루의 생산성은 그날 푼 문제 수와 난이도의 곱, 즉 $k_i \times r_i$입니다. $N$일 전체의 생산성 합이 최대가 되는 값을 구하세요.

여러 테스트 케이스가 주어지는 문제입니다. 첫 줄에 테스트 케이스의 수 $T$($1 \le T \le 100$)가 주어집니다.

각 테스트 케이스는 한 줄에 정수 $N$, $R$, $K$($1 \le N, R, K \le 10^9$)가 주어집니다.

각 테스트 케이스에 대해 생산성 합의 최댓값을 정수로 한 줄에 출력합니다.