You are given strings S and T, consisting of lowercase English letters. It is guaranteed that T is a permutation of the string abc. 

Find string S', the lexicographically smallest permutation of S such that T is not a subsequence of S'.

String a is a permutation of string b if the number of occurrences of each distinct character is the same in both strings.

A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero or all) elements.

A string a is lexicographically smaller than a string b if and only if one of the following holds:

  * a is a prefix of b, but a ≠ b;
  * in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Input

Each test contains multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a string S (1 ≤ |S| ≤ 100), consisting of lowercase English letters.

The second line of each test case contains a string T that is a permutation of the string abc. (Hence, |T| = 3).

Note that there is no limit on the sum of |S| across all test cases.

Output

For each test case, output a single string S', the lexicographically smallest permutation of S such that T is not a subsequence of S'.

Example

Input


7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc


Output


aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac

Note

In the first test case, both aaaabbc and aaaabcb are lexicographically smaller than aaaacbb, but they contain abc as a subsequence.

In the second test case, abccc is the smallest permutation of cccba and does not contain acb as a subsequence.

In the third test case, bcdis is the smallest permutation of dbsic and does not contain bac as a subsequence.
    import java.math.*;
    import java.io.*;
    import java.util.*;

    
//-------------------------------///////////////****/////////******//////////
//------------------------------------///**********//*****//********//*****//
//-----------------------------------///**********//*****//********//*****//
//----------------------------------///**********//*****//********//*****//
//---------------------------------///**********//*****//********//*****//
//--------------------------------///**********//*****//********//*****//
//--------------------------///**///**********//*****//********//*****//
//---------------------------/////***********/////////*******//////////

    
    public class CodeForces
    {
    	final static String no = "NO";
    	final static String yes = "YES";
    	static long count = 0;
    	
    	static public OutputWriter w = new OutputWriter(System.out);
    	static public FastScanner sc = new FastScanner();
    	

    	static HashMap<Integer,Integer> map = new HashMap<>();
    	
    	static Scanner fc = new Scanner(System.in);

//*******************************************Be SANSA**********************************************************
//************************************Don't stick to single approach********************************************	
//*****************************************You are a slow learner But you learn*********************************
//***************************************Don't fall in rating trap***********************************************
//**********************************Pain in temporary, regret remains forever************************************
    	
    	
        public static void main(String[] args) {
        	int test =sc.nextInt();
        	in:
        	while(test-->0) {
        		String s = sc.next();
        		String t = sc.next();
        		char[]ch = new char[s.length()];
        		for(int i=0;i<s.length();i++) {
        			ch[i] = s.charAt(i);
        		}
        		Arrays.sort(ch);
        		int i1 = -1;
        		int i2 = -1;
        		int i3 = -1;
        		for(int i=0;i<ch.length;i++)
        		{
        			if(ch[i]==t.charAt(0)) {
        				i1 = i;
        				break;
        			}
        		}
        		for(int i=0;i<ch.length;i++)
        		{
        			if(ch[i]==t.charAt(1)) {
        				i2 = i;
        				break;
        			}
        		}
        		for(int i=0;i<ch.length;i++)
        		{
        			if(ch[i]==t.charAt(2)) {
        				i3 = i;
        				break;
        			}
        		}
//        		
//        		w.writer.println(i1+" "+i2+" "+i3);
        		
        		if(i1==-1||i2==-1||i3==-1) {
        			for(int i=0;i<ch.length;i++) {
        				w.writer.print(ch[i]);
        			}
        			w.writer.println();
        			continue in;
        		}
        		else if (!(i1<i2 && i2<i3)) {
        			for(int i=0;i<ch.length;i++) {
        				w.writer.print(ch[i]);
        			}
        			w.writer.println();
        			continue in;
        		}
        		else {
        			char temp = ch[i3];
        			ch[i3] = ch[i2];
        			ch[i2] = temp;
        			for(int i=0;i<ch.length;i++) {
        				w.writer.print(ch[i]);
        			}
        			w.writer.println();
        			continue in;
        			
        		}
        		
        	}
        	w.writer.flush();	
        }
        
        static int sod(long  n) {
        	int res = 0;
        	while(n!=0) {
        		res+=n%10;
        		n = n/10;
        	}
			return res;
		}
		static class Pair {
            int visits, index;
            Pair(int visits, int index) {
                this.visits = visits;
                this.index = index;
            }
        }
        static public boolean checkBit(int n,int i){
            if((n>>i & 1)==1){
                return true;
            }else{
                return false;
            }
        }
        public static long pow(long a,long p)
        {
            long res=1;
            while(p>0)
            {
                if(p%2==1)
                {
                    p--;
                    res*=a;
                    res%=(long)1e9+7;
                }
                else
                {
                    a*=a;
                    a%=(long)1e9+7;
                    p/=2;
                }
            }
            return res;
        }
        static int gcd(int a, int b){
            if (a == 0)
                return b;
            return gcd(b % a, a);
        }
        static long gcd(long a, long b){
            if (a == 0)
                return b;
            return gcd(b % a, a);
        }
         
        // method to return LCM of two numbers
        static long lcm(long a, long b)
        {
            return (a / gcd(a, b)) * b;
        }
        static long getPairsCount(long[] arr, long sum)
        {
            Map<Long, Long> hm = new HashMap<>();
            int n = arr.length;
            long count = 0;
            for(int i =0;i<n;i++) {
            	if(hm.containsKey(sum - arr[i])) {
            		count+=hm.get(sum-arr[i]);
            	}
            	if(hm.get(arr[i])!=null) {
            		hm.put(arr[i], hm.get(arr[i])+1);
            	}
            	else {
            		hm.put(arr[i], 1l);
            	}
            }
            return count;
        }
        static long sumLong(int[]arr) {
        	long sum =0;
        	for(int x:arr) {
        		sum+=x;
        	}
        	return sum;
        }
        static boolean isEqualList(ArrayList<Integer> arr,ArrayList<Integer> temp){
            for(int i =0;i<arr.size();i++){
                if(arr.get(i)!=temp.get(i)){
                    return true;
                }
            }
            return false;
        }
    	static void sort(int[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
        }
     
        static void sort(long[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
        }
     
        static void sortDec(int[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
            int l = 0;
            int r = n - 1;
            while (l < r) {
                arr[l] ^= arr[r];
                arr[r] ^= arr[l];
                arr[l] ^= arr[r];
                l++;
                r--;
            }
        }
     
        static void sortDec(long[] arr) {
            Random rand = new Random();
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                int idx = rand.nextInt(n);
                if (idx == i) continue;
                arr[i] ^= arr[idx];
                arr[idx] ^= arr[i];
                arr[i] ^= arr[idx];
            }
            Arrays.sort(arr);
            int l = 0;
            int r = n - 1;
            while (l < r) {
                arr[l] ^= arr[r];
                arr[r] ^= arr[l];
                arr[l] ^= arr[r];
                l++;
                r--;
            }
        }
    	
    	
    	static int[] countInversions(int[]arr,int low,int high){
    		if(low==high) {
    			int base[] = new int[1];
    			base[0] = arr[low];
    			return base;
    		}
    		int mid = low+(high-low)/2;
    		int left[] = countInversions(arr,low,mid);
    		int right[] = countInversions(arr,mid+1,high);
    		int[]merged = merge(left,right);
    		return merged;
    	}
    	
    	
    	static int[] merge(int first[], int[]next) {
    		
    		int i = 0;
    		int j = 0;
    		int k = 0;
    		int[]merged = new int[first.length+next.length];
    		while(j<first.length && k<next.length) {
    			if(first[j]<=next[k]) {
    				merged[i++] = first[j++];
    			}else {
    				count += first.length -j;
    				merged[i++] = next[k++];
    				
    			}
    		}
    		while(j<first.length) {
    			merged[i++] = first[j++];
    		}
    		while(k<next.length) {
    			merged[i++] = next[k++];
    		}
    		return merged;
    	}
    	static class FastScanner {
    		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer st=new StringTokenizer("");
    		String next() {
    			while (!st.hasMoreTokens())
    				try {
    					st=new StringTokenizer(br.readLine());
    				} catch (IOException e) {
    					e.printStackTrace();
    				}
    			return st.nextToken();
    		}
    		
    		int nextInt() {
    			return Integer.parseInt(next());
    		}
    		int [] readArray(int n) {
    			int[] a=new int[n];
    			for (int i=0; i<n; i++) a[i]=nextInt();
    			return a;
    		}
    		long nextLong() {
    			return Long.parseLong(next());
    		}
    		long [] longArray(int n) {
    			long[] a=new long[n];
    			for(int i=0 ; i<n ; i++) a[i]=nextLong();
    			return a;
    		}
    		double nextDouble() {
    			return Double.parseDouble(next());
    		}
    	}
        static public class OutputWriter {
            private  final PrintWriter writer;
     
            public OutputWriter(OutputStream outputStream) {
                writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }
     
            public OutputWriter(Writer writer) {
                this.writer = new PrintWriter(writer);
            }
     
            public void print(Object... objects) {
                for (int i = 0; i < objects.length; i++) {
                    if (i != 0)
                        writer.print(' ');
                    writer.print(objects[i]);
                }
            }
     
            public void printLine(Object... objects) {
                print(objects);
                writer.println();
            }
     
            public void close() {
                writer.close();
            }
        }
     
     
    }