You are given a rectangle of height $H$ and width $W$. You must divide this rectangle exactly into three pieces such that each piece is a rectangle of integral height and width. You are required to minimize $Area_{max}-Area_{min}$ where $Area_{max}$ is the area of the largest rectangle and $Area_{min}$ is the area of the smallest rectangle, among all three rectangle pieces.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two space-separated integers $H$ and $W$ denoting the height and width of the rectangle.

Output format

For each test case, print the minimum possible value of $Area_{max}-Area_{min}$ in a new line.

Constraints

$1 \le T \le 1000\\ 2 \le H,W \le 200000$

• It is guaranteed that the sum of $H$ over $T$ test cases does not exceed $1e6$.
• It is guaranteed that the sum of $W$ over $T$ test cases does not exceed $1e6$.