B. Rutgers Bus Budgeting
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Due to budget reasons (the football team needs more DoorDash), Rutgers is working on updating its bus system. Currently, the bus system operates on an $$$n$$$ by $$$m$$$ rectangular grid, with bus stops in every cell and bus routes connecting horizontally or vertically adjacent stops. To do this and RUScrew over as many people as possible, Rutgers needs to remove 2 bus stops and all bus routes using those stops so that it's no longer possible to use the bus system to travel between every pair of remaining bus stops. Count the number of pairs of bus stops Rutgers can remove to do this.

Formally, given an $$$n$$$ by $$$m$$$ rectangular grid graph, count the number of pairs of vertices such that removing them and all incident edges makes the remaining graph disconnected.

Example of a 2 by 3 Rutgers bus system.
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2500$$$). The description of the test cases follows.

Each test case consists of a single line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 250$$$, $$$n \cdot m \ge 3$$$) — the dimensions of the Rutgers bus system.

Note that there is no limit on the sum of $$$n$$$ or $$$m$$$ over all test cases.

Output

For each test case, output a single integer — the number of pairs of bus stops Rutgers can remove to make it no longer possible to use the bus system to travel between every pair of remaining bus stops.

Example
Input
4
2 2
1 3
2 3
3 3
Output
2
0
5
4
Note

In the first test case, there are 6 ways to choose 2 bus stops to remove. 4 of these choices don't work. Removed stops are shown without a Rutgers logo.

The other 2 choices do work.