Background

Translated and simplified from ROIR 2022 D2T1.

Problem Description

Given three integers $n, a, b$, find how many pairs $(x, y)$ satisfy $0 \le x \le a$, $0 \le y \le b$, $x + y$ is not $0$, and $x + y$ is divisible by $n$.

Input Format

This problem has multiple test cases. The first line contains an integer $t$, representing the number of test cases.

The next $t$ lines each contain one test case: $n, a, b$, separated by spaces.

Output Format

For each test case, output one number per line, which is the number of valid $(x, y)$ pairs.

4
4 2 2
4 4 4
6 5 5
8 13 17

1
6
5
30

Hint

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le t \le 10^5$, $4 \le n \le 10^9$, and $0 \le a, b \le 10^9$.

Translated by ChatGPT 5