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.*;
import java.math.BigInteger;
 public class Solution
{
     static class Pair<A,B>{
        A parent;
        B rank;
        Pair(A parent,B rank)
        {
            this.rank=rank;
            this.parent=parent;
        }
    }
//    static int find(Pair pr[],int i)
//    {
//        if(i==pr[i].parent)
//            return i;
//        else
//        {
//            pr[i].parent=find(pr,pr[i].parent);
//            return pr[i].parent;
//        }
//    }
//    static void join(Pair[] pr,int i,int j)
//    {
//        i=find(pr,i);
//        j=find(pr,j);
//        if(i==j)
//            return;
//        if(pr[i].rank>=pr[j].rank)
//        {
//            pr[j].parent=i;
//            pr[i].rank+=pr[j].rank;
//        }
//        else
//        {
//            pr[i].parent = j;
//            pr[j].rank+=pr[i].rank;
//        }
//    }
    static void swap(char ar[],int i,int j)
    {
        char f = ar[i];
        ar[i]=ar[j];
        ar[j]=f;
    }
    static ArrayList<Integer> graph[];
    static int ans=0;
     static long powers(long n) 
    { 
        int MOD=1000000007;
        if (n <= 1) { 
            return 1; 
        }
        n--;
  
        // This is an identity matrix. 
        long res[][] = { { 1, 0 }, { 0, 1 } }; 
  
        // this is Transformation matrix. 
        long tMat[][] = { { 2, 2 }, { 1, 0 } };
        while (n > 0) { 
            if (n % 2 == 1) { 
                long tmp[][] = new long[2][2]; 
                tmp[0][0] = ((res[0][0] * tMat[0][0])%MOD 
                             + (res[0][1] * tMat[1][0])%MOD) 
                            %MOD;
                tmp[0][1] = ((res[0][0] * tMat[0][1])%MOD 
                             + (res[0][1] * tMat[1][1])%MOD) 
                            %MOD; 
                tmp[1][0] = ((res[1][0] * tMat[0][0])%MOD 
                             + (res[1][1] * tMat[1][0])%MOD) 
                            % MOD; 
                tmp[1][1] = ((res[1][0] * tMat[0][1])%MOD 
                             + (res[1][1] * tMat[1][1])%MOD) 
                            % MOD;
                res[0][0] = tmp[0][0]; 
                res[0][1] = tmp[0][1]; 
                res[1][0] = tmp[1][0]; 
                res[1][1] = tmp[1][1]; 
            } 
  
            n = n / 2; 
            long tmp[][] = new long[2][2]; 
            tmp[0][0] = ((tMat[0][0] * tMat[0][0])%MOD 
                         + (tMat[0][1] * tMat[1][0])%MOD) 
                        % MOD; 
            tmp[0][1] = ((tMat[0][0] * tMat[0][1])%MOD 
                         + (tMat[0][1] * tMat[1][1])%MOD) 
                        % MOD; 
            tmp[1][0] = ((tMat[1][0] * tMat[0][0])%MOD 
                         + (tMat[1][1] * tMat[1][0])%MOD) 
                        % MOD; 
            tmp[1][1] = ((tMat[1][0] * tMat[0][1])%MOD 
                         + (tMat[1][1] * tMat[1][1])%MOD) 
                        % MOD; 
            tMat[0][0] = tmp[0][0]; 
            tMat[0][1] = tmp[0][1]; 
            tMat[1][0] = tmp[1][0]; 
            tMat[1][1] = tmp[1][1]; 
        }
        return ((res[0][0]*6)%MOD + (res[0][1] * 2) % MOD)%MOD; 
    }
     static ArrayList<Integer> prime;
    public static void main (String[] args) throws IOException
    {
        StringBuilder sb = new StringBuilder();
        FastReader s1 = new FastReader();
        int t=s1.I();
        while(t--!=0)
        {
            int n=s1.I();
            long ar[]=new long[n];
            long br[]=new long[n];
            for(int i=0;i<n;i++)
            {
                ar[i]=s1.L();
                br[i]=s1.L();
            }
            long res[] = new long[n];
            res[0]=ar[0]-br[n-1];
            if(res[0]<0)
                res[0]=0;
            long sum=res[0];
            for(int i=1;i<n;i++)
            {
                res[i]=ar[i]-br[i-1];
                if(res[i]<0)
                    res[i]=0;
                sum+=res[i];
            }
            long min=Long.MAX_VALUE;
            for(int i=0;i<n;i++)
            {
                if(ar[i]+sum-res[i]<min)
                {
                    min=ar[i]+sum-res[i];
                }
            }
            sb.append(min+"\n");
        }
        System.out.println(sb);
    }
        static boolean check(long n)
    {
        if(n%2!=0)
        {
            return true;
        }
        else
        {
            if(n%4==0)
                return true;
            return false;
        }
    }
       static long computeXOR(long n) 
    { 
        // If n is a multiple of 4 
        if (n % 4 == 0) 
            return n; 
       
        // If n%4 gives remainder 1 
        if (n % 4 == 1) 
            return 1; 
       
        // If n%4 gives remainder 2 
        if (n % 4 == 2) 
            return n + 1; 
       
        // If n%4 gives remainder 3 
        return 0; 
    } 
     static void dfs(int index,int pc,int color[])
    {
        int c=0;
        BitSet bs= new BitSet(color.length+1);
        bs.set(color[index]);
        if(pc>=0)
        bs.set(pc);
        for(int i:graph[index])
        {
            if(color[i]==-1)
            {
                if(color[index]==c || pc==c)
                c=bs.nextClearBit(0);
                color[i]=c++;
                bs.set(c-1);
                dfs(i,color[index],color);
            }
        }
    }
    static void add1(TreeMap<Long,Integer> map,long key)
    {
        map.putIfAbsent(key, 0);
        map.replace(key, map.get(key)+1);
    }
    static void remove1(TreeMap<Long,Integer> map,long key)
    {
        map.replace(key, map.get(key)-1);
        if(map.get(key)==0)
            map.remove(key);
    }
    static void print(int h[])
    {
        for(int I:h)
            System.out.print(I+" ");
        System.out.println("");
    }
        static String preprocess(String s)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("@#");
        for(int i=0;i<s.length();i++)
        {
            sb.append(s.charAt(i)).append("#");
        }
        sb.append("$");
        return sb.toString();
    }
    static String LPS(String s)
    {
        String snew = preprocess(s);
        int n = snew.length();
//        System.out.println(snew);
        int c = 0,r = 0;
        int maxlen = 0;
        int index=0;
        int len[] = new int[n];
        for(int i=1;i<n-1;i++)
        {
            int mirr = c-(i-c);
            if(i<r)
            {
                len[i]=Math.min(len[mirr],r-i);
            }
      //      System.out.println(i+" ");
            while(snew.charAt(i+len[i])==snew.charAt(i-len[i]))
                len[i]++;
            if(i+len[i]>r)
            {
                c = i;
                r = i+len[i];
            }
//            System.out.println(c+" "+i+" "+snew.charAt(i)+" "+len[i]+" "+maxlen+" "+index);
            if(len[i]>maxlen)
            {
//                System.out.println("inside");
                maxlen = len[i];
                index = i;
            }
        }
        maxlen--;
        int left = (index-maxlen-1)/2;
        int right = left+maxlen;
        return s.substring(left, right);
    }
    static void phi(int n,HashMap<Integer,Integer> hm)
    {
        int large=0;
        for(int i=2;i<=Math.sqrt(n);i++)
        {
            if(n%i==0)
            {
                if(i>large)
                {
                    large=i;
                }
            }
            while(n%i==0)
            {
                n=n/i;
            }
        }
        if(n>1)
        {
            if(n>large)
                large=n;
        }
        hm.putIfAbsent(large, 0);
        hm.replace(large, hm.get(large)+1);
    }
    static ArrayList<Integer> primeFactor(int n)
    {
        ArrayList<Integer> ans = new ArrayList<>();
        if(n%2==0)
            ans.add(2);
        while (n%2==0)
        {   
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            if(n%i==0)
                ans.add(i);
            while (n%i == 0)
            {
                n /= i;
            }
        }
        if (n > 2)
            ans.add(n);
        return ans;
    }
    static int longestSubSeg(int a[], int n,int k)
    {
        int cnt0 = 0;
        int l = 0;
        int max_len = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0)
                cnt0++;
            while (cnt0 > k) {
                if (a[l] == 0)
                    cnt0--;
                l++;
            }
            max_len = Math.max(max_len, i - l + 1);
        }
        
        return max_len;
    }
    static int binary(int left,int right,long ar[],long no)
    {
        int mid=(left+right)/2;
        if(Math.abs(right-left)<=1)
        {
            if(no<=ar[left])
            {
                return left;
            }
            else
            {
                return right;
            }
        }
        if(ar[mid]==no)
            return mid;
        if(ar[mid]>no)
        {
            right=mid;
            return binary(left, right, ar, no);
        }
        else{
            left=mid;
            return binary(left, right, ar, no);
        }
    }
    static 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 I()
        {
            return Integer.parseInt(next());
        }
        
        long L()
        {
            return Long.parseLong(next());
        }
        
        double D()
        {
            return Double.parseDouble(next());
        }
        
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    static long gcd(long a,long b)
    {
        if(a%b==0)
            return b;
        return gcd(b,a%b);
    }
    static float power(float x, int y)
    {
        float temp;
        if( y == 0)
            return 1;
        temp = power(x, y/2);
        
        if (y%2 == 0)
            return temp*temp;
        else
        {
            if(y > 0)
                return x * temp * temp;
            else
                return (temp * temp) / x;
        }
    }
    static long pow(long x, long y)
    {
        int p =  1000000007;
        long res = 1;
        x = x % p;
        if(x<0)
            x+=p;
        while (y > 0)
        {
            if((y & 1)==1){
                res = (res * x) % p;
                if(res<0)
                    res+=p;
            }
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
    static void sieveOfEratosthenes(int n)
    {
        prime=new ArrayList<Integer>();
        boolean Prime[] = new boolean[n+1];
        for(int i=2;i<n;i++)
            Prime[i] = true;
        
        for(int p = 2; p*p <=n; p++)
        {
            if(Prime[p] == true)
            {
                prime.add(p);
                for(int i = p*p; i <= n; i += p)
                    Prime[i] = false;
            }
        }
    }
}