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$$.