Optimal Seating Arrangement

A classroom with code 15B03 has its desks arranged in an $n\times m$ grid, where each cell $(i,j)$ represents a desk. Due to exam regulations, any two desks remaining in the classroom must not be adjacent. Here, two desks $(i,j)$ and $(i',j')$ are defined to be adjacent if and only if \[ |i-i'|\le 1 \quad\text{and}\quad |j-j'|\le 1, \] i.e. they share at least one common point (including diagonally touching).

To satisfy the rule, the invigilator decides to remove some desks. His primary objective is to remove the minimum number of desks so that the remaining desks form what is known as a maximum independent set on the grid under the given adjacency relation. In other words, the remaining desks should be as many as possible.

However, to increase the challenge, he further requires that among all configurations that remove the minimum number of desks, the chosen configuration should maximize the sum of the distances over all remaining desks, where for each remaining desk, we take the Euclidean distance to the farthest remaining desk. Formally, if S is the set of remaining desks and for each p \(\in S\) the farthest distance is \[ d(p)=\max_{q\in S}\sqrt{(p_x-q_x)^2+(p_y-q_y)^2}, \] then the objective is to maximize: \[ \sum_{p\in S}d(p). \]

You are given multiple test cases. For each test case, given the dimensions of the grid, compute the maximum possible sum of the farthest Euclidean distances for the optimal configuration. It can be shown that an optimal strategy is to select all desks at positions with odd row and column indices (i.e. positions $(i,j)$ with i odd and j odd). Note that if n (or m) is even, then the largest odd number ≤ n (or m) is n-1 (or m-1). For each remaining desk at position (r, c), its farthest distance is the maximum of its Euclidean distances to the four extreme desks among those selected: \[ (1,1),\quad (1, C_2),\quad (R_2,1),\quad (R_2,C_2), \] where \[ R_2=\begin{cases} n, & \text{if } n\text{ is odd}\\ n-1, & \text{if } n\text{ is even} \end{cases}\quad\text{and}\quad C_2=\begin{cases} m, & \text{if } m\text{ is odd}\\ m-1, & \text{if } m\text{ is even.} \end{cases} \] Your task is to compute \[ \sum_{\substack{1\le r\le n,\, r\;\text{odd}\\1\le c\le m,\, c\;\text{odd}}}\max\Biggl\{\sqrt{(r-1)^2+(c-1)^2},\sqrt{(r-1)^2+(c-C_2)^2},\sqrt{(r-R_2)^2+(c-1)^2},\sqrt{(r-R_2)^2+(c-C_2)^2}\Biggr\}. \]

inputFormat

The first line of the input contains an integer T denoting the number of test cases. Each of the following T lines contains two integers n and m, which denote the number of rows and columns of the grid, respectively.

outputFormat

For each test case, output a single line containing the maximum sum of the farthest distances for the optimal configuration. The answer will be accepted if its absolute error does not exceed 10^{-6}.

sample

1
1 1

0.000000