小Q和小T在一张 $n$ 个点的完全无向图上玩游戏。在游戏的一开始，图中所有边都是黑色。他们会轮流操作 $m (m\ mod\ 2=0)$ 轮，小Q先手，即小Q将操作第 $1,3,5,…,m−1$ 轮，小T将操作第 $2,4,6,…,m$ 轮。每轮的操作方需要在图中选择恰好一条边，将其颜色进行反转，即由黑变白或者由白变黑，然后操作方将获得 $∑_{i=1}^n∑_{j=1}^ndis(i,j)$ 点得分，其中 $dis(i,j)$ 表示点 $i$ 到点 $j$ 的最短路径的长度。在所有 $m$ 轮操作结束之后，谁总分高谁就获胜。

在第 $i$ 轮中，每条黑边的长度都为 $a_i$，每条白边的长度都为 $b_i$。小Q和小T双方都知道所有 $m$ 轮的 $a,b$ 数据，且他们都会以最优策略进行操作，目标是让自己的总分减去对手的总分尽可能大。作为观战方的你，能否写一个程序预测最后双方的分差？

第一行包含一个正整数 $T (1≤T≤50)$，表示测试数据的组数。

每组数据第一行包含两个正整数 $n,m (2≤n≤8, 2≤m≤300, m\ mod\ 2=0)$，分别表示图中的点数以及游戏的轮数。

接下来 $m$ 行，每行两个正整数 $a_i,b_i (1≤a_i,b_i≤5)$，依次表示每轮中黑边和白边的长度。

输入数据保证 $∑m≤2000$。

对于每组数据输出一行一个整数，即最后小Q的总分减去小T的总分的值。