Problem: Vasya came up with a password to register for EatForces — a string s. The password in EatForces should be a string, consisting of lowercase and uppercase Latin letters and digits.

But since EatForces takes care of the security of its users, user passwords must contain at least one digit, at least one uppercase Latin letter and at least one lowercase Latin letter. For example, the passwords "abaCABA12", "Z7q" and "3R24m" are valid, and the passwords "qwerty", "qwerty12345" and "Password" are not. 

A substring of string s is a string x = s_l s_{l + 1} ... s_{l + len - 1} (1 ≤ l ≤ |s|, 0 ≤ len ≤ |s| - l + 1). len is the length of the substring. Note that the empty string is also considered a substring of s, it has the length 0.

Vasya's password, however, may come too weak for the security settings of EatForces. He likes his password, so he wants to replace some its substring with another string of the same length in order to satisfy the above conditions. This operation should be performed exactly once, and the chosen string should have the minimal possible length.

Note that the length of s should not change after the replacement of the substring, and the string itself should contain only lowercase and uppercase Latin letters and digits.

Input

The first line contains a single integer T (1 ≤ T ≤ 100) — the number of testcases.

Each of the next T lines contains the initial password s~(3 ≤ |s| ≤ 100), consisting of lowercase and uppercase Latin letters and digits.

Only T = 1 is allowed for hacks.

Output

For each testcase print a renewed password, which corresponds to given conditions. 

The length of the replaced substring is calculated as following: write down all the changed positions. If there are none, then the length is 0. Otherwise the length is the difference between the first and the last changed position plus one. For example, the length of the changed substring between the passwords "abcdef" → "a7cdEf" is 4, because the changed positions are 2 and 5, thus (5 - 2) + 1 = 4.

It is guaranteed that such a password always exists.

If there are several suitable passwords — output any of them.

Example

Input

2
abcDCE
htQw27


Output

abcD4E
htQw27

Note

In the first example Vasya's password lacks a digit, he replaces substring "C" with "4" and gets password "abcD4E". That means, he changed the substring of length 1.

In the second example Vasya's password is ok from the beginning, and nothing has to be changed. That is the same as replacing the empty substring with another empty substring (length 0).

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Stack;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.Map.Entry;

import static java.lang.Character.charCount;
import static java.lang.Character.codePointAt;
import static java.lang.Character.isSpaceChar;

public class GFGss
{
    static int mod1 = (int) (1e9 + 7);
    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
        public String nextString() throws IOException
        {
            String str00=scan.next();
            return str00;
        }
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do
            {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }

        public int[] nextArray(int n) throws IOException
        {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = nextInt();
            }
            return a;
        }
    }
    static boolean primeCheck(long num0)
    {
        boolean b1 = true;
        if(num0==1)
        {
            b1=false;
        }
        else
        {
            int num01 = (int) (Math.sqrt(num0)) + 1;
            me1: for (int i = 2; i < num01; i++)
            {
                if (num0 % i == 0)
                {
                    b1 = false;
                    break me1;
                }
            }
        }
        return b1;
    }
    static HashSet<Integer> primeDivisor(HashSet<Integer> hSet0,int num0)
    {
        boolean b1=primeCheck(num0);
        if(b1)
        {
            hSet0.add(num0);
        }
        else
        {
            for(int i=2;i*i<=num0;i++)
            {
                if(num0%i==0)
                {
                    hSet0.add(i);
                    while(num0%i==0)
                    {
                        num0 /= i;
                    }
                }
            }
            boolean b2=primeCheck(num0);
            if(b2)
            {
                hSet0.add(num0);
            }
        }
        return hSet0;
    }

    static long GCD (long num0,long num00)
    {
        BigInteger big1=BigInteger.valueOf(num0);
        BigInteger big2=BigInteger.valueOf(num00);
        big1=big1.gcd(big2);
        long num000=Long.parseLong(big1.toString());
        return num000;
    }

    static long power1 (long num0,long num00)
    {
        long res1 = 1;
        while (num00 > 0)
        {
            if (num00 % 2 != 0)
            {
                res1 = (res1 * (num0 % 100006)) % 1000016;
            }
            num0 *= num0;
            num0 %= 1000016;
            num00 /= 2;
        }
        return res1;
    }

    static HashSet<Integer> primeDivi(int num0)
    {
        HashSet<Integer> hSet1=new HashSet<>();
        int num00=(int)Math.sqrt(num0);
        hSet1.add(1);
        for(int i=2;i<num00+1;i++)
        {
            if(num0%i==0)
            {
                hSet1.add(i);
                hSet1.add(num0/i);
            }
        }
        return hSet1;
    }

    static long gcd(long num0,long num00)
    {
        if(num00==0)
        {
            return num0;
        }
        return gcd(num00,num0%num00);
    }


    public static void main(String[] args) throws IOException {
        //Reader r = new Reader();
        //PrintWriter writer=new PrintWriter(System.out);
        Scanner r = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        OutputWriter33 out33 = new OutputWriter33(System.out);

        int cas1=r.nextInt();
        while(cas1-->0)
        {
            String str1=r.next();
            char[] chrArr1=str1.toCharArray();
            int cap1=0,smal1=0,dig1=0;
            int len1=str1.length();

            for(int i=0;i<len1;i++)
            {
                char chr1=str1.charAt(i);
                if(chr1>64 && chr1<91)
                {
                    cap1++;
                }
                else if(chr1>96 && chr1<123)
                {
                    smal1++;
                }
                else
                {
                    dig1++;
                }
            }

            me1: if(cap1==0)
            {
                for (int i = 0; i < len1; i++)
                {
                    char chr2 = str1.charAt(i);
                    if(chr2>96 && chr2<123)
                    {
                        if(smal1>1)
                        {
                            chrArr1[i]='A';
                            break me1;
                        }
                    }
                    else
                    {
                        if(dig1>1)
                        {
                            chrArr1[i]='A';
                            break me1;
                        }
                    }
                }
            }

            me2: if(smal1==0)
            {
                for (int i = 0; i < len1; i++)
                {
                    char chr2 = str1.charAt(i);
                    if(chr2>64 && chr2<91)
                    {
                        if(cap1>1)
                        {
                            chrArr1[i]='a';
                            break me2;
                        }
                    }
                    else
                    {
                        if(dig1>1)
                        {
                            chrArr1[i]='a';
                            break me2;
                        }
                    }
                }
            }

            me1: if(dig1==0)
            {
                for (int i = 0; i < len1; i++)
                {
                    char chr2 = str1.charAt(i);
                    if(chr2>96 && chr2<123)
                    {
                        if(smal1>1)
                        {
                            chrArr1[i]='1';
                            break me1;
                        }
                    }
                    else
                    {
                        if(cap1>1)
                        {
                            chrArr1[i]='1';
                            break me1;
                        }
                    }
                }
            }

            if(cap1==0 && smal1==0)
            {
                chrArr1[0]='A';
                chrArr1[1]='a';
            }
            else if(cap1==0 && dig1==0)
            {
                chrArr1[0]='A';
                chrArr1[1]='1';
            }
            else if(smal1==0 && dig1==0)
            {
                chrArr1[0]='a';
                chrArr1[1]='1';
            }

            str1="";
            for(int i=0;i<len1;i++)
            {
                str1+=chrArr1[i];
            }

            out33.print(str1+"\n");
        }
        r.close();
        out33.close();
    }
}
class OutputWriter33
{
    BufferedWriter writer;

    public OutputWriter33(OutputStream stream)
    {
        writer = new BufferedWriter(new OutputStreamWriter(stream));
    }

    public void print(int i) throws IOException
    {
        writer.write(i + "");
    }

    public void println(int i) throws IOException
    {
        writer.write(i + "\n");
    }

    public void print(String s) throws IOException
    {
        writer.write(s + "");
    }

    public void println(String s) throws IOException
    {
        writer.write(s + "\n");
    }

    public void print(char[] c) throws IOException
    {
        writer.write(c);
    }

    public void close() throws IOException
    {
        writer.close();
    }
}