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>
				/*
				TO LEARN
				1-segment trees
				2-euler tour
			
				*/
				/*
				TO SOLVE 
				uva 1103
				codeforces 722 kavi on pairing duty
				*/
				/*
				bit manipulation shit
				1-Computer Systems: A Programmer's Perspective
				2-hacker's delight
				3-(02-03-bits-ints)
				4-machine-basics
				5-Bits Manipulation tutorialspoint
				*/
				/*
				TO WATCH
				1-what is bitmasking by kartik arora youtube
				*/
				            import java.util.*;
						    import java.math.*;
						    import java.io.*; 
						    import java.util.stream.Collectors;

						       public class A{
						     
						  static InputStream inputStream = System.in;
				            static FastScanner scan=new FastScanner();
						     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static void brute(long arr1[],long arr2[],long arr3[])
	{
		for(int i=0;i<arr1.length;i++)
		{
			for(int j=0;j<arr3.length;j++)
			{
				long fin=Long.MAX_VALUE;
				long res=0;
				for(int k=0;k<arr2.length;k++)
				{
					long cur=(arr1[i]-arr3[j])*(arr1[i]-arr3[j]);
					cur+=(arr1[i]-arr2[k])*(arr1[i]-arr2[k]);
					cur+=(arr2[k]-arr3[j])*(arr2[k]-arr3[j]);
					if(cur<fin)
					{
						res=arr2[k];
						fin=cur;
					}
					out.println(arr1[i]+" "+arr3[j]+" "+arr2[k]+" "+cur);
				}
				
			}
		}
	}
	static long check(long arr1[],long arr2[],long arr3[])
	{
		int n1=arr1.length,n2=arr2.length,n3=arr3.length;
		TreeSet<Long>set2=new TreeSet<Long>();
		TreeSet<Long>set3=new TreeSet<Long>();
		for(int i=0;i<n2;i++)
			set2.add(arr2[i]);
		for(int i=0;i<n3;i++)
			set3.add(arr3[i]);
		int l=0,r=n3-1;
		//out.println(Arrays.toString(arr3));
		long res=Long.MAX_VALUE;
		for(long k:arr1)
		{
			Long high=set2.higher(k-1),low=set3.lower(k+1);
			if(high==null||low==null)
				continue;
			res=Math.min(res,(low-high)*(low-high)+(low-k)*(low-k)+(high-k)*(high-k));
		}
		return res;
	}
	static boolean does(Pair p1,Pair p2)
	{
	//	System.out.println("F "+ p1);
	//	System.out.println("S "+ p2);
		if(p2.x>p1.x&&p2.x<p1.y&&p2.y>p1.y)
			return true;
		return false;
	}

					public static void main(String[] args)  throws Exception 
				      {
					
							///scan=new FastScanner("cownomics.in");
						//out = new PrintWriter("cownomics.out");
						 
						 /*
						 currently doing 
						 1-digit dp
						 2-ds like fenwick and interval tree and sparse table 
						 */
						 /*
						 READING 
						 1-Everything About Dynamic Programming codeforces
						 2-DYNAMIC PROGRAMMING: FROM NOVICE TO ADVANCED topcoder
						 3-Introduction to DP with Bitmasking codefoces
						 4-Bit Manipulation hackerearth
						 5-read more about mobious and inculsion-exclusion 
						 */
			/*
			1-choose some range x and y and then find the closest to the mid which is (x+y)/2
			2-

			*/


						    int tt=1;
						tt=scan.nextInt();
						int T=tt;
						

					 outer:while(tt-->0)
						    {
						    	int n=scan.nextInt(),k=scan.nextInt();
						    	Pair pairs[]=new Pair[n];
						    	boolean used[]=new boolean[2*n];
						    	for(int i=0;i<k;i++)
						    	{
						    		int x=scan.nextInt()-1,y=scan.nextInt()-1;
						    	used[x]=true;
						    	used[y]=true;
						    pairs[i]=new Pair(Math.min(x,y),Math.max(x,y));
						    	}			
						    	ArrayList<Integer>notused=new ArrayList<Integer>();
						    	for(int i=0;i<2*n;i++)
						    		if(!used[i])
						    			notused.add(i);
						    	//	out.println(notused);
						    		int l=0,r=notused.size()/2;
						    		for(int i=k;i<n;i++)
						    		{
						    			pairs[i]=new Pair(notused.get(l),notused.get(r));
						    			
l++;
r++;	
						    		}
						    		int ans=0;
						    		for(Pair p1:pairs){
						    			for(Pair p2:pairs){
						    			//	out.println(p1);
						    			//	out.println(p2);
						    				if(does(p1,p2)){
						    					//out.println(p1);
						    					//out.println(p2);
						    					ans++;
						    				}}
						    			}
						    				out.println(ans);
						    		   				
						    		}
out.close();
			}
 public static class EndPoint 
    {
        public int point;
        public boolean isStart;
        
        public EndPoint(int point, boolean isStart) 
        {
            this.point = point;
            this.isStart = isStart;
        }
    }
    
    // comparator for class end-point
    public static class EndPointCmp implements Comparator<EndPoint>
    {
        @Override
        public int compare(EndPoint o1, EndPoint o2) 
        {
            return o1.point - o2.point;
        }
        
    }
    
						static class special{
							boolean bool;
							long n;
							//int id;
							special(boolean bool,long n)
							{
								this.bool=bool;
								this.n=n;
							}
							@Override
							    public int hashCode() {
						                int hash = 7;
			    hash = 31 * hash + (int) n;
			   
			    return hash;
						            }
						              @Override
						            public boolean equals(Object o){
						                if (o == this) return true;
						                if (o.getClass() != getClass()) return false;
						                special t = (special)o;
						                return t.bool == bool && t.n == n;
						            }
						}

						   
						     static long binexp(long a,long n)
						    {
						        if(n==0)
						            return 1;
						        long res=binexp(a,n/2);
						        if(n%2==1)
						            return res*res*a;
						        else 
						            return res*res;
						    }
						     
						    static long powMod(long base, long exp, long mod) {
						           if (base == 0 || base == 1) return base;
						           if (exp == 0) return 1;
						           if (exp == 1) return (base % mod+mod)%mod;
						           long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
						           R *= R;
						           R %= mod;
						           if ((exp & 1) == 1) {
						               return (base * R % mod+mod)%mod;
						           }
						           else return (R %mod+mod)%mod;
						       }
						    static double dis(double x1,double y1,double x2,double y2)
						    {
						        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
						    }
						    static long mod(long x,long y)
						        {
						            if(x<0)
						                x=x+(-x/y+1)*y;
						            return x%y;
						        }
						     public static  long pow(long b, long e) {
						                long r = 1;
						                while (e > 0) {
						                    if (e % 2 == 1) r = r * b ;
						                    b = b * b;
						                    e >>= 1;
						                }
						                return r;
						            }
						    private static void sort(long[] arr) {
						            List<Long> list = new ArrayList<>();
						            for (long object : arr) list.add(object);
						            Collections.sort(list);
						        //Collections.reverse(list);
						            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
						        }
						    private static void sort2(long[] arr) {
						            List<Long> list = new ArrayList<>();
						            for (Long object : arr) list.add(object);
						            Collections.sort(list);
						        Collections.reverse(list);
						            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
						        }
						     static class FastScanner
				{
				    private int BS = 1 << 16;
				    private char NC = (char) 0;
				    private byte[] buf = new byte[BS];
				    private int bId = 0, size = 0;
				    private char c = NC;
				    private double cnt = 1;
				    private BufferedInputStream in;
				 
				    public FastScanner() {
				        in = new BufferedInputStream(System.in, BS);
				    }
				 
				    public FastScanner(String s) {
				        try {
				            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
				        } catch (Exception e) {
				            in = new BufferedInputStream(System.in, BS);
				        }
				    }
				 
				    private char getChar() {
				        while (bId == size) {
				            try {
				                size = in.read(buf);
				            } catch (Exception e) {
				                return NC;
				            }
				            if (size == -1) return NC;
				            bId = 0;
				        }
				        return (char) buf[bId++];
				    }
				 
				    public int nextInt() {
				        return (int) nextLong();
				    }
				 
				    public int[] nextInts(int N) {
				        int[] res = new int[N];
				        for (int i = 0; i < N; i++) {
				            res[i] = (int) nextLong();
				        }
				        return res;
				    }
				 
				    public long[] nextLongs(int N) {
				        long[] res = new long[N];
				        for (int i = 0; i < N; i++) {
				            res[i] = nextLong();
				        }
				        return res;
				    }
				 
				    public long nextLong() {
				        cnt = 1;
				        boolean neg = false;
				        if (c == NC) c = getChar();
				        for (; (c < '0' || c > '9'); c = getChar()) {
				            if (c == '-') neg = true;
				        }
				        long res = 0;
				        for (; c >= '0' && c <= '9'; c = getChar()) {
				            res = (res << 3) + (res << 1) + c - '0';
				            cnt *= 10;
				        }
				        return neg ? -res : res;
				    }
				 
				    public double nextDouble() {
				        double cur = nextLong();
				        return c != '.' ? cur : cur + nextLong() / cnt;
				    }
				 
				    public double[] nextDoubles(int N) {
				        double[] res = new double[N];
				        for (int i = 0; i < N; i++) {
				            res[i] = nextDouble();
				        }
				        return res;
				    }
				 
				    public String next() {
				        StringBuilder res = new StringBuilder();
				        while (c <= 32) c = getChar();
				        while (c > 32) {
				            res.append(c);
				            c = getChar();
				        }
				        return res.toString();
				    }
				 
				    public String nextLine() {
				        StringBuilder res = new StringBuilder();
				        while (c <= 32) c = getChar();
				        while (c != '\n') {
				            res.append(c);
				            c = getChar();
				        }
				        return res.toString();
				    }
				 
				    public boolean hasNext() {
				        if (c > 32) return true;
				        while (true) {
				            c = getChar();
				            if (c == NC) return false;
				            else if (c > 32) return true;
				        }
				    }
				}

						     static class Pair implements Comparable<Pair>{
						            public long x, y,z;
						            public Pair(long x1, long y1,long z1) {
						                x=x1;
						                y=y1;
						                z=z1;
						            }
						             public Pair(long x1, long y1) {
						                x=x1;
						                y=y1;
						    
						            }
						            
						            @Override
						            public int hashCode() {
						                return (int)(x + 31 * y);
						            }
						            public String toString() {
						                return x + " " + y+" "+z;
						            }
						            @Override
						            public boolean equals(Object o){
						                if (o == this) return true;
						                if (o.getClass() != getClass()) return false;
						                Pair t = (Pair)o;
						                return t.x == x && t.y == y&&t.z==z;
						            }
						    public int compareTo(Pair o)
						    {
						    	
						    
						    	return (int)((o.y-o.x)-(y-x));
						     
						        }
						     
						    }
						    
						    }

						     
