В поисках пропитания большая дружная семья кроликов добрела до морковного поля. К сожалению, чуть раньше сюда же прибыла большая дружная семья голодных хомяков. Во избежание конфликта было решено собирать урожай по очереди. Поле представляет собой \textbf{n }грядок по \textbf{m }кустов; на каждом кусте растет некоторое количество морковок. Очередной собирающий стартует от любого куста первой грядки и движется к последней, переходя от одного куста к другому по следующему правилу: от куста номер \textbf{k }на грядке \textbf{l }можно перейти только на грядку \textbf{l + 1 }к одному из трех кустов с номерами \textbf{k - 1}, \textbf{k}, \textbf{k + 1} (конечно, если кусты с такими номерами есть). Каждый посещенный куст очищается от моркови полностью. Первым на сбор урожая выходит один из кроликов, следом идет хомяк, потом снова кролик и так до тех пор, пока на поле есть хоть одна морковка. Кролики суетливы, поэтому они выбирают путь наиболее выгодный внешне: стартуют от самого богатого куста первой грядки, а из трех последующих вариантов всегда выбирают самый большой куст (при наличии нескольких кустов с одинаковым числом морковок выбирается куст с наибольшим номером). Хомяки, прибыв на поле раньше, успели составить подробную карту поля и поддерживают её в актуальном состоянии на основе оперативных данных о сборе урожая, поэтому они для каждого хомяка выбирают путь, позволяющий собрать максимальное количество морковок из возможных (при наличии нескольких вариантов с максимально возможным количеством морковок выбирается путь через куст с наибольшим номером). По известной карте поля определите, сколько моркови удалось собрать кроликам и хомякам по отдельности. \InputFile Первая строка содержит количество тестов. Каждый тест начинается с двух целых чисел \textbf{n} и \textbf{m} (\textbf{1 }≤ \textbf{n}, \textbf{m} ≤ \textbf{100}). Следом идут \textbf{n }строк, в каждой из которых \textbf{m }чисел \textbf{X_i}_\{,\}\textbf{_j} (\textbf{0 }≤\textbf{ x_i}_\{,\}\textbf{_j} ≤ \textbf{10}). \textbf{x_i_\{,\}_j} - количество морковок на \textbf{j}-ом кусте \textbf{i}-ой грядки. \OutputFile Для каждого теста в отдельной строке выведите два числа: количество морковок, собранных кроликами и хомяками, соответственно.