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>
//Utilities
import java.io.*;
import java.util.*;

public class C {
	static int t;
	static int n, k;
	static int l;
	static int[] x, y;
	static ArrayList<Integer> addX, addY;
	static boolean[] done;
	static int res;
	
	public static void main(String[] args) throws IOException {
		t = in.iscan();
		outer : while (t-- > 0) {
			n = in.iscan(); k = in.iscan();
			x = new int[k]; y = new int[k];
			for (int i = 0; i < k; i++) {
				x[i] = in.iscan(); y[i] = in.iscan();
				if (x[i] > y[i]) {
					int tmp = y[i];
					y[i] = x[i];
					x[i] = tmp;
				}
			}
			if (k == 0) {
				out.println(n*(n-1)/2);
				continue outer;
			}
			res = 0;
			done = new boolean[2*n+1];
			addX = new ArrayList<Integer>(); addY = new ArrayList<Integer>();
			int shift = x[0] == 1 ? 0 : 2*n - x[0] + 1;
			for (int i = 0; i < k; i++) {
				if (x[i] + shift <= 2*n) x[i] += shift;
				else x[i] = (x[i] + shift) % (2*n);
				if (y[i] + shift <= 2*n) y[i] += shift;
				else y[i] = (y[i] + shift) % (2*n);
				if (x[i] > y[i]) {
					int tmp = y[i];
					y[i] = x[i];
					x[i] = tmp;
				}
				done[x[i]] = true; done[y[i]] = true;
				updateIntersections(x[i], y[i]);
			}
//			out.println("RES: " + res);
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			for (int i = 2; i <= 2*n; i++) {
				if (done[i]) {
					continue;
				}
				tmp.add(i);
			}
//			out.println(l + " " + tmp);
			for (int i = 0; i < tmp.size()/2; i++) {
				updateIntersections(tmp.get(i), tmp.get(i+tmp.size()/2));
//				out.println(tmp.get(i) + " " + tmp.get(i+tmp.size()/2) + " " + res);
			}
			out.println(res);
		}
		out.close();
	} 
	
	static void updateIntersections(int curX, int curY) {
		for (int i = 0; i < addX.size(); i++) {
			if (sideBetween(curX, addX.get(i), addY.get(i)) != sideBetween(curY, addX.get(i), addY.get(i))) {
				res++;
			}
		}
		addX.add(curX); addY.add(curY);
		done[curX] = true; done[curY] = true;
	}
	
	static int sideBetween(int x, int l2, int r2) {
		if (l2 < x && x < r2) {
			return 0;
		}
		else {
			return 1;
		}
	}
	
	static INPUT in = new INPUT(System.in);
	static PrintWriter out = new PrintWriter(System.out);
	private static class INPUT {

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar, numChars;

		public INPUT (InputStream stream) {
			this.stream = stream;
		}

		public INPUT (String file) throws IOException {
			this.stream = new FileInputStream (file);
		}

		public int cscan () throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read (buf);
			}
			
			if (numChars == -1)
				return numChars;

			return buf[curChar++];
		}

		public int iscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			int res = 0;

			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));

			return res * sgn;
		}

		public String sscan () throws IOException {
			int c = cscan ();
			
			while (space (c))
				c = cscan ();

			StringBuilder res = new StringBuilder ();

			do {
				res.appendCodePoint (c);
				c = cscan ();
			}
			while (!space (c));

			return res.toString ();
		}

		public double dscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			double res = 0;

			while (!space (c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * UTILITIES.fast_pow (10, iscan ());
				
				res *= 10;
				res += c - '0';
				c = cscan ();
			}

			if (c == '.') {
				c = cscan ();
				double m = 1;

				while (!space (c)) {
					if (c == 'e' || c == 'E')
						return res * UTILITIES.fast_pow (10, iscan ());

					m /= 10;
					res += (c - '0') * m;
					c = cscan ();
				}
			}

			return res * sgn;
		}

		public long lscan () throws IOException {
			int c = cscan (), sgn = 1;
			
			while (space (c))
				c = cscan ();

			if (c == '-') {
				sgn = -1;
				c = cscan ();
			}

			long res = 0;

			do {
				res = (res << 1) + (res << 3);
				res += c - '0';
				c = cscan ();
			}
			while (!space (c));

			return res * sgn;
		}

		public boolean space (int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

	public static class UTILITIES {

		static final double EPS = 10e-6;
		
		public static void sort(int[] a, boolean increasing) {
			ArrayList<Integer> arr = new ArrayList<Integer>();
			int n = a.length;
			for (int i = 0; i < n; i++) {
				arr.add(a[i]);
			}
			Collections.sort(arr);
			for (int i = 0; i < n; i++) {
				if (increasing) {
					a[i] = arr.get(i);
				}
				else {
					a[i] = arr.get(n-1-i);
				}
			}
		}
		
		public static void sort(long[] a, boolean increasing) {
			ArrayList<Long> arr = new ArrayList<Long>();
			int n = a.length;
			for (int i = 0; i < n; i++) {
				arr.add(a[i]);
			}
			Collections.sort(arr);
			for (int i = 0; i < n; i++) {
				if (increasing) {
					a[i] = arr.get(i);
				}
				else {
					a[i] = arr.get(n-1-i);
				}
			}
		}
		
		public static void sort(double[] a, boolean increasing) {
			ArrayList<Double> arr = new ArrayList<Double>();
			int n = a.length;
			for (int i = 0; i < n; i++) {
				arr.add(a[i]);
			}
			Collections.sort(arr);
			for (int i = 0; i < n; i++) {
				if (increasing) {
					a[i] = arr.get(i);
				}
				else {
					a[i] = arr.get(n-1-i);
				}
			}
		}

		public static int lower_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;

			while (low < high) {
				mid = (low + high) / 2;

				if (arr[mid] >= x)
					high = mid;
				else
					low = mid + 1;
			}

			return low;
		}

		public static int upper_bound (int[] arr, int x) {
			int low = 0, high = arr.length, mid = -1;

			while (low < high) {
				mid = (low + high) / 2;

				if (arr[mid] > x)
					high = mid;
				else
					low = mid + 1;
			}

			return low;
		}

		public static int gcd (int a, int b) {
			return b == 0 ? a : gcd (b, a % b);
		}

		public static int lcm (int a, int b) {
			return a * b / gcd (a, b);
		}

		public static long fast_pow_mod (long b, long x, int mod) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow_mod (b * b % mod, x / 2, mod) % mod;

			return b * fast_pow_mod (b * b % mod, x / 2, mod) % mod;
		}

		public static int fast_pow (int b, int x) {
			if (x == 0) return 1;
			if (x == 1) return b;
			if (x % 2 == 0) return fast_pow (b * b, x / 2);

			return b * fast_pow (b * b, x / 2);
		}

		public static long choose (long n, long k) {
			k = Math.min (k, n - k);
			long val = 1;

			for (int i = 0; i < k; ++i)
				val = val * (n - i) / (i + 1);

			return val;
		}

		public static long permute (int n, int k) {
			if (n < k) return 0;
			long val = 1;

			for (int i = 0; i < k; ++i)
				val = (val * (n - i));

			return val;
		}
		
		// start of permutation and lower/upper bound template
		public static void nextPermutation(int[] nums) {
		    //find first decreasing digit
		    int mark = -1;
		    for (int i = nums.length - 1; i > 0; i--) {
		        if (nums[i] > nums[i - 1]) {
		            mark = i - 1;
		            break;
		        }
		    }
		 
		    if (mark == -1) {
		        reverse(nums, 0, nums.length - 1);
		        return;
		    }
		 
		    int idx = nums.length-1;
		    for (int i = nums.length-1; i >= mark+1; i--) {
		        if (nums[i] > nums[mark]) {
		            idx = i;
		            break;
		        }
		    }
		 
		    swap(nums, mark, idx);
		 
		    reverse(nums, mark + 1, nums.length - 1);
		}
		 
		public static void swap(int[] nums, int i, int j) {
		    int t = nums[i];
		    nums[i] = nums[j];
		    nums[j] = t;
		}
		 
		public static void reverse(int[] nums, int i, int j) {
		    while (i < j) {
		        swap(nums, i, j);
		        i++;
		        j--;
		    }
		}
		
		static int lower_bound (int[] arr, int hi, int cmp) {
			int low = 0, high = hi, mid = -1;
			while (low < high) {
				mid = (low + high) / 2;
				if (arr[mid] >= cmp) high = mid;
				else low = mid + 1;
			}
			return low;
		}
	 
		static int upper_bound (int[] arr, int hi, int cmp) {
			int low = 0, high = hi, mid = -1;
			while (low < high) {
				mid = (low + high) / 2;
				if (arr[mid] > cmp) high = mid;
				else low = mid + 1;
			}
			return low;
		}
		// end of permutation and lower/upper bound template
	}
}
