You are given an array consisting of n integers a_1, a_2, ..., a_n. Initially a_x = 1, all other elements are equal to 0.

You have to perform m operations. During the i-th operation, you choose two indices c and d such that l_i ≤ c, d ≤ r_i, and swap a_c and a_d.

Calculate the number of indices k such that it is possible to choose the operations so that a_k = 1 in the end.

Input

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

The first line of each test case contains three integers n, x and m (1 ≤ n ≤ 10^9; 1 ≤ m ≤ 100; 1 ≤ x ≤ n).

Each of next m lines contains the descriptions of the operations; the i-th line contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n).

Output

For each test case print one integer — the number of indices k such that it is possible to choose the operations so that a_k = 1 in the end.

Example

Input


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


Output


6
2
3

Note

In the first test case, it is possible to achieve a_k = 1 for every k. To do so, you may use the following operations:

  1. swap a_k and a_4; 
  2. swap a_2 and a_2; 
  3. swap a_5 and a_5. 



In the second test case, only k = 1 and k = 2 are possible answers. To achieve a_1 = 1, you have to swap a_1 and a_1 during the second operation. To achieve a_2 = 1, you have to swap a_1 and a_2 during the second operation.
	import java.io.BufferedReader;
						import java.io.FileReader;
						import java.io.IOException;
						import java.io.InputStreamReader;
						import java.io.PrintWriter;
				import java.lang.reflect.Array;
				import java.math.BigInteger;
						import java.util.*;
			
							  public class Codeforces{
								  private static long [] catalan= new long[2501];
								  private static final int MOD=1000000007;
	
	
								    void pre() throws Exception{}
								    void solve(int TC) throws Exception{ 
								    	int t=ni();
								    	while(t--!=0) {
								    		int n=ni();
								    		int x=ni();
								    		int m=ni();
								    		//int a[]=new int[n+1];
								
								    		int flag=0;
								    		int cur_min=x;
								    		int cur_max=x;
								    		for(int i=0;i<m;i++) {
								    			int a1=ni();
								    			int b1=ni();
								    			
								    			
								    			if(Math.max(cur_min,a1)<=Math.min(b1,cur_max))
								    			{
								    			cur_min=Math.min(cur_min,a1);
								    			cur_max=Math.max(cur_max,b1);
								    			}
								    			
								    			}
								    		
								    		pn(cur_max-cur_min+1);
								    	}
								   
								        }
								    
	
								    				
								    
				
								    static boolean multipleTC = false, memory = false;
								    FastReader in;PrintWriter out;
								    void run() throws Exception{
								        in = new FastReader();
								        out = new PrintWriter(System.out);
								        int T = (multipleTC)?ni():1;
								        pre();for(int t = 1; t<= T; t++)solve(t);
								        out.flush();
								        out.close();
								    }
								    public static void main(String[] args) throws Exception{
								        if(memory)new Thread(null, new Runnable() {public void run(){try{new Codeforces().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
								        else new Codeforces().run();
								    }
								    void p(Object o){out.print(o);}
								    void pn(Object o){out.println(o);}
								    void nd(Object o){out.println(o);}
								    void pni(Object o){out.println(o);out.flush();}
								    String n()throws Exception{return in.next();}
								    String nln()throws Exception{return in.nextLine();}
								    int ni()throws Exception{return Integer.parseInt(in.next());}
								    long nl()throws Exception{return Long.parseLong(in.next());}
								    double nd()throws Exception{return Double.parseDouble(in.next());}
								    
								    class FastReader{
								        BufferedReader br;
								        StringTokenizer st;
								        public FastReader(){
								            br = new BufferedReader(new InputStreamReader(System.in));
								        }
								
								        public FastReader(String s) throws Exception{
								            br = new BufferedReader(new FileReader(s));
								        }
								
								        String next() throws Exception{
								            while (st == null || !st.hasMoreElements()){
								                try{
								                    st = new StringTokenizer(br.readLine());
								                }catch (IOException  e){
								                    throw new Exception(e.toString());
								                }
								            }
								            return st.nextToken();
								        }
								
								        String nextLine() throws Exception{
								            String str = "";
								            try{   
									                str = br.readLine();
									            }catch (IOException e){
								                throw new Exception(e.toString());
								            }  
								            return str;
								        }
								    }
								}