You are playing another computer game, and now you have to slay n monsters. These monsters are standing in a circle, numbered clockwise from 1 to n. Initially, the i-th monster has a_i health.

You may shoot the monsters to kill them. Each shot requires exactly one bullet and decreases the health of the targeted monster by 1 (deals 1 damage to it). Furthermore, when the health of some monster i becomes 0 or less than 0, it dies and explodes, dealing b_i damage to the next monster (monster i + 1, if i < n, or monster 1, if i = n). If the next monster is already dead, then nothing happens. If the explosion kills the next monster, it explodes too, damaging the monster after it and possibly triggering another explosion, and so on.

You have to calculate the minimum number of bullets you have to fire to kill all n monsters in the circle.

Input

The first line contains one integer T (1 ≤ T ≤ 150000) — the number of test cases.

Then the test cases follow, each test case begins with a line containing one integer n (2 ≤ n ≤ 300000) — the number of monsters. Then n lines follow, each containing two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10^{12}) — the parameters of the i-th monster in the circle.

It is guaranteed that the total number of monsters in all test cases does not exceed 300000.

Output

For each test case, print one integer — the minimum number of bullets you have to fire to kill all of the monsters.

Example

Input


1
3
7 15
2 14
5 3


Output


6
import java.util.*;
import java.io.*;



public class Main{
    static long m=998244353l;
    static int[] lp=new int[4];
    static int[] rp=new int[4];
    static ArrayList<ArrayList> prob;
    public static void main(String[] args) throws IOException{
        FastReader sc=new FastReader();
        BufferedOutputStream out=new BufferedOutputStream(System.out);
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            long[][] abi=new long[n][2];
            for(int i=0;i<n;i++){
                abi[i][0]=sc.nextLong();abi[i][1]=sc.nextLong();
            }
            long[] minreq=new long[n];
            long tot=0l;
            for(int i=1;i<=n;i++){
                minreq[i%n]=(long)Math.max(abi[i%n][0]-abi[(i-1)%n][1],0);
                tot+=minreq[i%n];
            }
            long ans=Long.MAX_VALUE;
            for(int i=0;i<n;i++){
                long cur=tot-minreq[i]+abi[i][0];
                ans=Math.min(cur,ans);
            }
            out.write((ans+"\n").getBytes());
        }
        out.flush();
    }


    public static long cnt_sum_k_subar(long[] a,int n,int k){
        HashMap<Long,Long> map=new HashMap<Long,Long>();
        long ret=0;
        long cur_sum=0;
        for(int i=0;i<n;i++){
            cur_sum+=a[i];
            if(cur_sum==k){
                ret++;
            }
            if(map.containsKey(cur_sum-k)){
                ret+=map.get(cur_sum-k);
            }
            if(map.containsKey(cur_sum)){
                map.put(cur_sum, map.get(cur_sum)+1);
            }
            else{
                map.put(cur_sum, (long)1);
            }
        }
        return ret;
    }



    public static ArrayList<Integer> lcm(int num){
        ArrayList<Integer> arrl=new ArrayList<Integer>();
        while(num%2==0){
            arrl.add(2);
            num/=2;
        }
        for(int i=3;i*i<=num;i+=2){
            while(num%i==0){
                arrl.add(i);
                num/=i;
            }
        }
        if(num>2){
            arrl.add(num);
        }
        return arrl;
    }


    static long modInverse(long a,long m) 
    { 
        long m0 = m; 
        long y = 0l, x = 1l; 
  
        if (m == 1) 
            return 0l; 
  
        while (a > 1) 
        { 
  
            long q = a / m; 
  
            long t = m; 
  
            m = a % m; 
            a = t; 
            t = y; 
  
            y = x - q * y; 
            x = t; 
        } 
        if (x < 0) 
            x += m0; 
  
        return x; 
    } 



    public static int num_fact(int num){
        int cnt=0;
        for(int i=1;i*i<=num;i++){
            if(num%i==0){
                if(i*i==num){
                    cnt+=1;
                }
                else{
                    cnt+=2;
                }
            }
        }
        return cnt;
    }


    public static long cal(int k,int x){
        long val=1;

        for(int i=0;i<k;i++){
            val*=2;
            if(val>x){
                break;
            }
        }
        return val;
    }

    public static void sort_inc(int[][] arr,int col){        //change dimention if req
        Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(final int[] entry1,final int[] entry2) { 
                if (entry1[col] > entry2[col]) 
                    return 1; 
                else
                    return -1; 
            }
        });
    }


    public static boolean prime(int n){
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }


    static int gcd(int a, int b) 
	{ 
	if (b == 0) 
		return a; 
	return gcd(b, a % b); 
	} 
}


class FastReader{ 
    BufferedReader br; 
    StringTokenizer st; 

    public FastReader(){ 
        br = new BufferedReader(new
                 InputStreamReader(System.in)); 
    } 
  
    String next(){ 
        while (st == null || !st.hasMoreElements()){ 
            try{ 
                st = new StringTokenizer(br.readLine()); 
            } 
            catch (IOException  e){ 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 
  
    int nextInt(){ 
        return Integer.parseInt(next()); 
    } 
  
    long nextLong(){ 
        return Long.parseLong(next()); 
    }
  
    double nextDouble(){ 
        return Double.parseDouble(next()); 
    }
  
    String nextLine(){ 
        String str = ""; 
        try{ 
            str = br.readLine(); 
        }
        catch (IOException e){ 
            e.printStackTrace(); 
        }
        return str; 
    }
}