write a go solution for E1. Turtle and Inversions (Easy Version)time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is an easy version of this problem. The differences between the versions are the constraint on m and r_i<l_i+1 holds for each i from 1 to m-1 in the easy version. You can make hacks only if both versions of the problem are solved.Turtle gives you m intervals [l_1,r_1],[l_2,r_2],ldots,[l_m,r_m]. He thinks that a permutation p is interesting if there exists an integer k_i for every interval (l_i<=k_i<r_i), and if he lets a_i=maxlimits_j=l_i^k_ip_j,b_i=minlimits_j=k_i+1^r_ip_j for every integer i from 1 to m, the following condition holds:\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_iTurtle wants you to calculate the maximum number of inversions of all interesting permutations of length n, or tell him if there is no interesting permutation.An inversion of a permutation p is a pair of integers (i,j) (1<=i<j<=n) such that p_i>p_j.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^3). The description of the test cases follows.The first line of each test case contains two integers n,m (2<=n<=5*10^3,0<=m<=n/2) — the length of the permutation and the number of intervals.The i-th of the following m lines contains two integers l_i,r_i (1<=l_i<r_i<=n) — the i-th interval.Additional constraint on the input in this version: r_i<l_i+1 holds for each i from 1 to m-1.It is guaranteed that the sum of n over all test cases does not exceed 5*10^3.OutputFor each test case, if there is no interesting permutation, output a single integer -1.Otherwise, output a single integer — the maximum number of inversions.ExampleInput62 02 11 25 12 48 21 46 87 21 34 77 31 23 45 6Output1
0
8
21
15
15
NoteIn the third test case, the interesting permutation with the maximum number of inversions is [5,2,4,3,1].In the fourth test case, the interesting permutation with the maximum number of inversions is [4,8,7,6,3,2,1,5]. In this case, we can let [k_1,k_2]=[1,7].In the fifth test case, the interesting permutation with the maximum number of inversions is [4,7,6,3,2,1,5].In the sixth test case, the interesting permutation with the maximum number of inversions is [4,7,3,6,2,5,1].. Output only the code with no comments, explanation, or additional text.