B. Игра в казино
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известное во всей солнечной системе казино «Галактика удачи» вводит новую карточную игру.

В этой игре есть колода из $$$n$$$ карт. На каждой карте написано $$$m$$$ чисел. Каждый из $$$n$$$ игроков получает ровно по одной карте из колоды.

Далее все игроки попарно играют друг с другом, причем каждая пара игроков играет ровно один раз. Таким образом, если всего, например, четыре игрока, то будет сыграно шесть игр: первый со вторым, первый с третьим, первый с четвертым, второй с третьим, второй с четвертым и третий с четвертым.

В каждой из таких игр некоторым образом определяется победитель, но правила здесь довольно сложны, поэтому мы не будем описывать их здесь. Важно лишь, какое число фишек выплачивается победителю. Пусть на карте первого игрока записаны числа $$$a_1, a_2, \dots, a_m$$$, а на карте второго игрока — $$$b_1, b_2, \dots, b_m$$$. Тогда победителю выплачивается $$$|a_1 - b_1| + |a_2 - b_2| + \dots + |a_m - b_m|$$$ фишек из общего банка, где $$$|x|$$$ обозначает модуль числа $$$x$$$.

Чтобы определить размер общего банка, необходимо вычислить суммарный выигрыш победителей по всем играм. Поскольку карт в колоде и игроков может быть много, то Вам было поручено написать программу, которая выполняет все необходимые вычисления.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных находится два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \cdot m \le 3\cdot 10^5$$$) — количество карт в колоде и количество чисел на одной карте.

В каждой из следующих $$$n$$$ строк набора входных данных находится по $$$m$$$ целых чисел $$$c_{i,j}$$$ ($$$1 \le c_{i,j} \le 10^6$$$) — описание $$$i$$$-й карты.

Гарантируется, что общая сумма $$$n \cdot m$$$ во всех тестах не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — суммарный размер выигрышей по всем играм.

Пример
Входные данные
3
3 5
1 4 2 8 5
7 9 2 1 4
3 8 5 3 1
1 4
4 15 1 10
4 3
1 2 3
3 2 1
1 2 1
4 2 7
Выходные данные
50
0
31
Примечание

Рассмотрим первый набор входных данных.

В игре между первым и вторым игроком победитель получит $$$|1-7| + |4-9| + |2-2| + |8-1| + |5-4| = 19$$$ фишек.

В игре между первым и третьим игроком победитель получит $$$|1-3| + |4-8| + |2-5| + |8-3| + |5-1| = 18$$$ фишек.

В игре между вторым и третьим игроком победитель получит $$$|7-3| + |9-8| + |2-5| + |1-3| + |4-1| = 13$$$ фишек.

Итого за игру будет разыграно $$$19 + 18 + 13 = 50$$$ фишек.