除了「吃飯、睡覺、打東東」的老故事以外，作為 2021 年的 IOI 銀牌，東東發憤圖強想在 World Final 加冕宇宙冠軍，而發憤圖強就要從發憤塗牆開始。
牆壁可以視為一個 $H \times W$ 的棋盤，每個格子需要被漆成黑色或是白色。東東身為一個分治大師，決定採用分治的方法來完成著色，具體來說，東東採取的策略如下：

• 如果當前要塗色的矩形內部所有格子全部都是黑色或白色，那東東可以動用「打東東之術」在一瞬間（$0$ 單位時間內）就將其塗色完成。
• 否則，東東可以選一條水平或垂直線將其分割成兩個矩形（理所當然分割線不能選在格子上，要選在格子和格子之間），如果把兩個矩形塗色的時間分別是 $c_1$ 和 $c_2$，那東東就可以在 $\max(c_1,c_2)+1$ 的時間將原本的矩形著色完成。

由於東東想要趕快完成塗色去 $n$ 刷桐生可可的畢業直播，因此他在每次分割的時候都會選擇能最小化總時間的分割方式。
作為一個油宅，你也想看桐生可可的畢業直播，那麼你能計算出來東東會花多久的時間在粉刷牆壁上，方便你結束之後趕過去跟東東一起看嗎？