Description

我们已知扫雷游戏是 \(m\times n\) 格（即 \(n\) 行 \(m\) 列），其中有一些(=  =)雷，每个雷都要与至少一个数字相邻（上下左右斜对），没有雷的地方是一个 \(0\) ~ \(8\) 的数字，代表 \(8\) 个相邻格子里雷的个数（苛性氢：然而 \(0\) 是不可能出现的~）。
那么，该棋盘里最多可以有多少个雷呢？

Format

Input

本题有多组数据。
对于每组数据，为两个大于等于 \(2\) 的正整数，\(m\) 和 \(n\)（空格隔开）；
最后一行为两个 \(0\)（空格隔开）。

Output

对于每组数据，一个正整数：可以放的最多雷数（保证在 \(\[0,2^{63})\) 之内）。

Sample 1

Input

2 2
3 4
10 10
0 0

Output

3
10
84

Limitation

对于 \(25\%\) 的数据，\(m,n\le 10\)，数据组数 \(T\le 3\)；
对于 \(75\%\) 的数据，\(m,n\le 200\)，数据组数 \(T\le 10\)；
对于 \(100\%\) 的数据，\(m,n< 2^{31}\)，数据组数 \(T\le 10^5\)。

Hint

样例解释:（以下x代表雷,1~8代表相应数字）
    x x
    x 3
解释:至少需要1个数字与其余3个雷相邻
    x x x
    x 8 x
    x x x
    x 5 x
解释:第一个数字只能有8个雷与之相邻，第四排还需有1个数字

    x x x x x x x x x x
    x 8 x x 8 x x 8 x 5
    x x x x x x x x x x
    x x x x x x x x x x
    x 8 x x 8 x x 8 x 5
    x x x x x x x x x x
    x x x x x x x x x x
    x 8 x x 8 x x 8 x 5
    x x x x x x x x x x
    x 8 x x 8 x x 8 x 3
解释:自己看去吧=ω=  话说苛性氢在背景里的解就是把加粗的3个雷换成数字~

苛性氢:你们用dp好了~  一个皇后不能被8个皇后包围的n皇后问题~

ZYS:好像在样例3的解释里数字分布有某种规律啊？每3*3的唔$%^#^%& （←被捂嘴）

Source

By hydrogenhydroxide