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:
/**
 * created by vidyut on 20/09/18
 **/
import java.io.*;
import java.util.*;
import java.math.*;

public class A {
    public static void main(String[] args) {
        try {
            InputReader in = new InputReader(System.in);
            BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
            int tc = in.readInt();
            for (int t = 0; t < tc; t++) {
                char a[] = in.readLine().toCharArray();
                int n = a.length;
                boolean hasUp = false;
                boolean hasL = false;
                boolean hasN = false;
                int countU = 0, countL = 0, countN = 0;
                for (int i = 0; i < n; i++) {
                    if (Character.isUpperCase(a[i])) {
                        hasUp = true;
                        countU++;
                    }
                    else if(Character.isLowerCase(a[i])) {
                        hasL = true;
                        countL++;
                    }
                    else if (Character.isDigit(a[i])) {
                        hasN = true;
                        countN++;
                    }
                }
                if (hasL && hasN && hasUp) {
                }
                else if (hasL && hasN) {
                    if (countL >= countN) {
                        for (int i = 0; i < n; i++) {
                            if (Character.isLowerCase(a[i])) {
                                a[i] = Character.toUpperCase(a[i]);
                                break;
                            }
                        }
                    }
                    else {
                        for (int i = 0; i < n; i++) {
                            if (Character.isDigit(a[i])) {
                                a[i] = Character.toUpperCase('A');
                                break;
                            }
                        }
                    }
                }
                else if (hasUp && hasN) {
                    if (countU >= countN) {
                        for (int i = 0; i < n; i++) {
                            if (Character.isUpperCase(a[i])) {
                                a[i] = Character.toLowerCase(a[i]);
                                break;
                            }
                        }
                    }
                    else {
                        for (int i = 0; i < n; i++) {
                            if (Character.isDigit(a[i])) {
                                a[i] = Character.toLowerCase('a');
                                break;
                            }
                        }
                    }
                }
                else if (hasUp && hasL) {
                    if (countU >= countL) {
                        for (int i = 0; i < n; i++) {
                            if (Character.isUpperCase(a[i])) {
                                a[i] = '1';
                                break;
                            }
                        }
                    }
                    else {
                        for (int i = 0; i < n; i++) {
                            if (Character.isLowerCase(a[i])) {
                                a[i] = '1';
                                break;
                            }
                        }
                    }
                }
                else if (hasL) {
                    a[0] = 'A';
                    a[1] = '1';
                }
                else if (hasUp) {
                    a[0] = 'a';
                    a[1] = '1';
                }
                else if (hasN) {
                    a[0] = 'A';
                    a[1] = 'a';
                }
                else {
                    a[0] = 'A';
                    a[1] = 'a';
                    a[2] = '1';
                }
                out.write(a);
                out.newLine();
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
class InputReader {
    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int peek() {
        if (numChars == -1)
            return -1;
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int length = readInt();
        if (length < 0)
            return null;
        byte[] bytes = new byte[length];
        for (int i = 0; i < length; i++)
            bytes[i] = (byte) read();
        try {
            return new String(bytes, "UTF-8");
        } catch (UnsupportedEncodingException e) {
            return new String(bytes);
        }
    }

    public static boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuffer buf = new StringBuffer();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r')
                buf.appendCodePoint(c);
            c = read();
        }
        return buf.toString();
    }

    public String readLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String readLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines)
            return readLine();
        else
            return readLine0();
    }

    public BigInteger readBigInteger() {
        try {
            return new BigInteger(readString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char readCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return readString();
    }

    public boolean readBoolean() {
        return readInt() == 1;
    }
}