题目描述

小Q和小T在一张 $n$ 个点的完全无向图上玩游戏。在游戏的一开始，图中所有边都是黑色。他们会轮流操作 $m$ ($m\ \text{mod}\ 2=0$) 轮，小Q先手，即小Q将操作第 $1,3,5,…,m−1$ 轮，小T将操作第 $2,4,6,…,m$ 轮。每轮的操作方需要在图中选择恰好一条边，将其颜色进行反转，即由黑变白或者由白变黑，然后操作方将获得 $∑\limits ^n_{i=1}∑\limits ^n_{j=1}dis(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\ \text{mod}\ 2=0$)，分别表示图中的点数以及游戏的轮数。

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

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

输出格式

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

输入样例

2
2 4
1 2
3 1
5 3
2 5
5 4
1 1
2 2
3 5
5 2

输出样例

0
-56