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.io.*;
import java.util.*;

public class Solution {

    /* -------------------------------------- Main Start ----------------------------------- */
    
    private static String s;
    private static boolean found;
    public static void main(String[] args) throws IOException {
        FastReader fs = new FastReader();
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(fs.nextLine());
        while(t-- > 0){
            char[] str = fs.nextLine().toCharArray();
            String perm = fs.nextLine();
            Arrays.sort(str);
            String k = String.valueOf(str);
            boolean one = false, two = false, three = false;
            for(char i : str){
                if(i == 'a') one = true;
                else if(i == 'b') two = true;
                else if(i == 'c') three = true;
            }
            if(one && two && three){
                String a = "";
                int b = 0, c = 0;
                String non = "";
                for(char i: str){
                    if(i == 'a') a += 'a';
                    else if(i == 'b') b++;
                    else if(i == 'c') c++;
                    else non += i;
                }
                boolean bFirst = false;
                for(int i = 0; i < 3; i++){
                    if(perm.charAt(i) == 'b'){
                        bFirst = true;
                        break;
                    }
                    if(perm.charAt(i) == 'c') break;
                }
                if(bFirst){
                    while(c-- > 0) a += 'c';
                    while(b-- > 0) a += 'b';
                    for(char i: non.toCharArray()) a += i;
                }
                else{
                    while(b-- > 0) a += 'b';
                    while(c-- > 0) a += 'c';
                    
                    for(char i: non.toCharArray()) a += i;
                }
                System.out.println(a);
            }
            else{
                System.out.println(str);
            }
        } 
    }
    
    
  
    /* ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- 

      StringBuilder sb = new StringBuilder();
      sb.append(x + "\n");
    
      Collections.sort(arr, (a, b) -> Integer.compare(a[0], b[0]))
      arr.toArray(new int[arr.size()][])
      
      List<List<Integer>> pair = new ArrayList<>();
      pair.add(Arrays.asList(nums[i], nums[j],-sum));
    
     */
    private static final int MOD_1 = 1000000000 + 7;

    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        /* --------------------------------------------------------------------------------------------------------------------------------------------------------------------- */
        void printArray(int[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void printArray(String[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void printArray(long[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void print(int data) {
            System.out.println(data);
        }

        void print(String data) {
            System.out.println(data);
        }

        void print(long data) {
            System.out.println(data);
        }

        int[] II(int n) throws IOException {
            int[] d = new int[n];
            String[] arr = nextLine().split(" ");
            for (int i = 0; i < n; i++) {
                d[i] = Integer.parseInt(arr[i]);
            }

            return d;
        }

        String[] IS(int n) throws IOException {
            return nextLine().split(" ");
        }

        long[] IL(int n) throws IOException {
            long[] d = new long[n];
            String[] arr = nextLine().split(" ");
            for (int i = 0; i < n; i++) {
                d[i] = Long.parseLong(arr[i]);
            }
            return d;
        }

        public long gcd(long a, long b) {
            if (a == 0) {
                return b;
            }
            return gcd(b % a, a);
        }

        public long power(long x, long y, long p) {
            long res = 1;
            x = x % p;
            if (x == 0) {
                return 0;
            }

            while (y > 0) {
                if ((y & 1) == 1) {
                    res = (res * x) % p;
                }
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }

        void sieveOfEratosthenes(boolean prime[], int size) {
            Arrays.fill(prime, true);
            prime[0] = prime[1] = false;
            prime[2] = true;

            for (int p = 2; p * p < size; p++) {
                if (prime[p] == true) {
                    for (int i = p * p; i < size; i += p) {
                        prime[i] = false;
                    }
                }
            }
        }

        public long fact(long n) {
            long ans = 1;
            for (int i = 2; i <= n; i++) {
                ans = (ans * i) % MOD_1;
            }
            return ans;
        }

        public long lcm(long a, long b) {
            return (a * b) / gcd(a, b);
        }

        public int log2(int N) {
            int result = (int) (Math.log(N) / Math.log(2));
            return result;
        }

        // find first element in the arr that is equal to the x. 
        // If x is not present in arr then it will return first element that is greater than x
        // It return arr.size() if all element are smaller than x
        public int lowerBound(int[] a, int x) {
            int l=-1,r=a.length;
            while(l+1<r) {
              int m=(l+r)>>>1;
              if(a[m]>=x) r=m;
              else l=m;
            }
            return r;
        }

        // find first element in the arr that is greater than x. 
        // It return arr.size() if all element are smaller than x
        public int upperBound(int[] a, int x) {
            int l=-1,r=a.length;
            while(l+1<r) {
               int m=(l+r)>>>1;
               if(a[m]<=x) l=m;
               else r=m;
            }
            return l+1;
        }

    }

}
