11044 - Searching for Nessy

有關尼斯湖水怪請參考：http://en.wikipedia.org/wiki/Loch_Ness_Monster

2003年7月，BBC廣播團隊發表一則關於尼斯湖水怪的研究，該研究利用了600個獨立的聲納探測儀後發現，尼斯湖內並無任何大型生物，所以該團隊認為尼斯湖水怪並不存在。如今，我們想要重複實作此實驗。

湖的大小定為 n 列與 m 行，6n, m10000，在湖中佈滿聲納探測儀，用來偵測湖上的動靜，其中：

1. 探測儀可偵測的範圍為九宮格的大小，如下圖X點及其相鄰的八個區塊。

2. 湖邊四周圍並不需要偵測，因為湖水太淺，水怪不會游到這邊來。

X點表示聲納所在位置，而灰色區域表示可偵測的範圍，如上圖。

Input

輸入的第一行為整數 t 表示測試資料的組數，每一組資料一行有兩個以空白隔開的整數 n, m，6n, m10000，表示湖的大小(n 列 m 行)。

Output

請對每一組輸入資料，輸出最少需要幾組聲納儀才能使偵測範圈涵蓋所有監控區域。

Sample Input

3
6 6
7 7
9 13

Sample Output

4
4
12

---

原文出處