Кубик
Останнім часом настільні ігри набули великої популярності. У наше життя повертаються як давно забуті, так і нові захоплюючі ігри. Ви отримали нову, унікальну настільну гру. Для цієї гри потрібен гральний кубик (його розгортка наведена на рисунку) і прямокутне ігрове поле, розділене на клітинки. У кожній клітинці поля записано ціле число.
Грають кілька людей за такими правилами:
Першим ходом гравець ставить кубик у ліву верхню клітинку поля на будь-яку грань.
Кожним наступним ходом гравець переходить на сусідню клітинку праворуч або вниз, перекочуючи кубик на одну з 4 сусідніх граней.
За кожен хід гравець отримує K·A очок, де A - число в поточній клітинці поля, а K - цифра на грані кубика, якою він стоїть на ігровому полі.
Гравець продовжує ходити, поки не досягне нижньої правої клітинки поля. Тоді очки за всі його ходи підсумовуються.
Коли один гравець завершує хід, починає наступний гравець, і так далі.
Переможцем стає гравець, який набрав найбільше очок.
За заданим ігровим полем визначте максимальну суму очок, яку можна отримати, граючи за цими правилами.
Вхідні дані
Перша стрічка вхідного файлу містить T - кількість тестів (T ≤ 200). Перша стрічка кожного тесту містить числа N і M, розділені пробілом, - розміри ігрового поля (1 ≤ N·M ≤ 10^5). Далі йде N рядків по M чисел, розділених пробілами, - числа, записані в клітинках ігрового поля. Всі числа за модулем не перевищують 10^3.
Вихідні дані
Для кожного тесту в окремому рядку виведіть одне ціле число - максимальну кількість очок, яку можна отримати при оптимальній грі.