On a circle lie 2n distinct points, with the following property: however you choose 3 chords that connect 3 disjoint pairs of points, no point strictly inside the circle belongs to all 3 chords. The points are numbered 1,   2,   ...,   2n in clockwise order.

Initially, k chords connect k pairs of points, in such a way that all the 2k endpoints of these chords are distinct.

You want to draw n - k additional chords that connect the remaining 2(n - k) points (each point must be an endpoint of exactly one chord).

In the end, let x be the total number of intersections among all n chords. Compute the maximum value that x can attain if you choose the n - k chords optimally.

Note that the exact position of the 2n points is not relevant, as long as the property stated in the first paragraph holds.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ n) — half the number of points and the number of chords initially drawn.

Then k lines follow. The i-th of them contains two integers x_i and y_i (1 ≤ x_i,   y_i ≤ 2n, x_i ≠ y_i) — the endpoints of the i-th chord. It is guaranteed that the 2k numbers x_1,   y_1,   x_2,   y_2,   ...,   x_k,   y_k are all distinct.

Output

For each test case, output the maximum number of intersections that can be obtained by drawing n - k additional chords.

Example

Input


4
4 2
8 2
1 5
1 1
2 1
2 0
10 6
14 6
2 20
9 10
13 18
15 12
11 7


Output


4
0
1
14

Note

In the first test case, there are three ways to draw the 2 additional chords, shown below (black chords are the ones initially drawn, while red chords are the new ones):

<image>

We see that the third way gives the maximum number of intersections, namely 4.

In the second test case, there are no more chords to draw. Of course, with only one chord present there are no intersections.

In the third test case, we can make at most one intersection by drawing chords 1-3 and 2-4, as shown below:

<image>
import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType

sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP

graphDict = collections.defaultdict

queue = collections.deque


################## pypy deep recursion handling ##############
# Author = @pajenegod
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        to = f(*args, **kwargs)
        if stack:
            return to
        else:
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        return to
                    to = stack[-1].send(to)

    return wrappedfunc


################## Graphs ###################
class Graphs:
    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes, psf):
        global ans
        if len(visited_nodes.keys()) == n:
            ans = psf
            return
        visited_nodes[nodes] = None
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes, psf + [neighbour])
        visited_nodes.pop(nodes)
        return

    def dfs(self, node):
        global ans
        Visited = collections.OrderedDict()
        self.dfs_utility(node, Visited, [node])

    def bfs(self, node):
        visited = set()
        if node not in visited:
            queue.append(node)
            visited.add(node)
        while queue:
            parent = queue.popleft()
            print(parent)
            for item in self.graph[parent]:
                if item not in visited:
                    queue.append(item)
                    visited.add(item)


################### Tree Implementaion ##############
class Tree:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def inorder(node, lis):
    if node:
        inorder(node.left, lis)
        lis.append(node.data)
        inorder(node.right, lis)
    return lis


def leaf_node_sum(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.data
    return leaf_node_sum(root.left) + leaf_node_sum(root.right)


def hight(root):
    if root is None:
        return -1
    if root.left is None and root.right is None:
        return 0
    return max(hight(root.left), hight(root.right)) + 1


#################################################

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0), []))


def p_sum(array):
    return list(itertools.accumulate(array))


################################ <fast I/O> ###########################################
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


#############################################<I/O Region >##############################################


def inp():
    return sys.stdin.readline().strip()


def map_inp(v_type):
    return map(v_type, inp().split())


def list_inp(v_type):
    return list(map_inp(v_type))


######################################## Solution ####################################

for _ in range(int(inp())):
    n, k = map_inp(int)
    paired = []
    all_points = set([item for item in range(1, (2 * n) + 1)])
    for i in range(k):
        a, b = map_inp(int)
        paired.append([min(a, b), max(a, b)])
        all_points.remove(a)
        all_points.remove(b)
    rem_points = list(sorted(all_points))
    best_rem_pairing = []
    for i in range(len(rem_points) // 2):
        best_rem_pairing.append([rem_points[i], rem_points[len(rem_points) - 1 - i]])
    ans = math.comb(len(rem_points) // 2, 2)
    temp = best_rem_pairing + paired
    visited = set()
    for item in paired:
        for it in temp:
            if tuple(it) in visited:
                continue
            if item == it:
                continue
            if item[0] < it[0] < item[1] < it[1] or it[0] < item[0] < it[1] < item[1]:
                ans += 1
            visited.add(tuple(item))
    print(ans)
