d039: 11044 - Searching for Nessy

內容：

尼斯湖水怪是一隻住在尼斯湖中神秘且不明的動物。尼斯湖則是北蘇格蘭的印芬尼斯市附近的一個大且深的淡水湖。尼斯怪通常被視為一種湖怪。

背景

2003 年 7 月，BBC (英國國家廣播電視公司) 曾報導了一項他們對尼斯湖所作的大規模研究，他們用 600 支聲納也沒有辦法在湖中找到任何「水怪」(也就是任何已知或未知的大型動物) 的踪跡。他們推論尼斯怪並不存在。現在我們要重覆這項實驗。

問題

給你一個 n 列 m 行的格子代表尼斯湖，6 ≤ n, m ≤ 10000，找出最少要放幾個聲納才能控制所有的方格，條件如下：

例如，

其中 X 代表聲納，灰色區域則是它所監控的範圍。最後一個圖則是一組可接受的解答。

輸入說明

輸入的第一行有一個整數，t，代表測試筆數。每筆測資一行，含有兩個由空白分開的數字，6 ≤ n, m ≤ 10000，也就是格子的大小 (n 列 m 行)。

輸出說明：

每筆測資輸出一行，顯示符合上述條件的最小數字。

範例輸入：

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。

6 6

7 7

9 13

範例輸出：

提示：

出處：

UVa ACM 11044 (管理：snail)