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.
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2
from fractions import Fraction

t = int(input())
for _ in range(t):
    n,x, m = map(int, input().split())
    flag = 0
    rsf = [-1, -1]
    for tup in range(m):
        l, r = map(int, input().split())
        if l <= x <= r or flag:
            flag = 1
            if rsf == [-1, -1]: 
                rsf = [l, r]
            else:
                # if they intersect
                if l <= rsf[0] <= r or l <= rsf[1] <= r:
                    rsf = [min(rsf[0], l), max(rsf[1], r)]

    print((rsf[1] - rsf[0] + 1) if rsf != [-1, -1] else 1)

    
                

        
