This is the hard version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string s, consisting of lowercase English letters. Find the longest string, t, which satisfies the following conditions: 

  * The length of t does not exceed the length of s. 
  * t is a palindrome. 
  * There exists two strings a and b (possibly empty), such that t = a + b ( "+" represents concatenation), and a is prefix of s while b is suffix of s. 

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^5), the number of test cases. The next t lines each describe a test case.

Each test case is a non-empty string s, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed 10^6.

Output

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.

Example

Input


5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba


Output


a
abcdfdcba
xyzyx
c
abba

Note

In the first test, the string s = "a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:

  * Its length is 9, which does not exceed the length of the string s, which equals 11. 
  * It is a palindrome. 
  * "abcdfdcba" = "abcdfdc" + "ba", and "abcdfdc" is a prefix of s while "ba" is a suffix of s. 



It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" = "c" + "" and a or b can be empty. The other possible solution for this test is "s".
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.function.IntUnaryOperator;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            TaskD solver = new TaskD();
            int testCount = Integer.parseInt(in.next());
            for (int i = 1; i <= testCount; i++)
                solver.solve(i, in, out);
            out.close();
        }
    }

    static class TaskD {
        int limit = 1000100;
        char[] s = new char[limit];
        HashData hd31 = new HashData(limit, (int) 1e9 + 7, 31);
        HashData hd61 = new HashData(limit, (int) 1e9 + 7, 61);
        PartialHash ph31 = new PartialHash(hd31);
        PartialHash ph61 = new PartialHash(hd61);
        PartialHash revPh31 = new PartialHash(hd31);
        PartialHash revPh61 = new PartialHash(hd61);
        int n;

        int mirror(int x) {
            return n - 1 - x;
        }

        boolean isP(int l, int r) {
            int revL = mirror(r);
            int revR = mirror(l);
            return ph31.hash(l, r, false) == revPh31.hash(revL, revR, false) &&
                    ph61.hash(l, r, false) == revPh61.hash(revL, revR, false);
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            n = in.readString(s, 0);

            ph31.populate(i -> s[i], 0, n - 1);
            ph61.populate(i -> s[i], 0, n - 1);
            revPh31.populate(i -> s[n - 1 - i], 0, n - 1);
            revPh61.populate(i -> s[n - 1 - i], 0, n - 1);


            int l = 0;
            int r = n - 1;
            while (l < r && s[l] == s[r]) {
                l++;
                r--;
            }

            int pre = r;
            int post = l;
            while (!isP(l, pre)) {
                pre--;
            }
            while (!isP(post, r)) {
                post++;
            }
            if (pre - l > r - post) {
                l = pre;
                r++;
            } else {
                r = post;
                l--;
            }

            for (int i = 0; i <= l; i++) {
                out.append(s[i]);
            }
            for (int i = r; i < n; i++) {
                out.append(s[i]);
            }
            out.println();
        }

    }

    static class Power {
        final Modular modular;

        public Power(Modular modular) {
            this.modular = modular;
        }

        public int pow(int x, int n) {
            if (n == 0) {
                return modular.valueOf(1);
            }
            long r = pow(x, n >> 1);
            r = modular.valueOf(r * r);
            if ((n & 1) == 1) {
                r = modular.valueOf(r * x);
            }
            return (int) r;
        }

        public int inverseByFermat(int x) {
            return pow(x, modular.m - 2);
        }

    }

    static class PartialHash {
        HashData hd;
        int[] hash;

        public PartialHash(HashData hd) {
            this.hd = hd;
            hash = new int[hd.pow.length];
        }

        public void populate(IntUnaryOperator function, int l, int r) {
            if (l > 0) {
                hash[l - 1] = 0;
            }
            hash[l] = hd.mod.mul(function.applyAsInt(l), hd.pow[l]);
            for (int i = l + 1; i <= r; i++) {
                hash[i] = hd.mod.valueOf(hash[i - 1] + hd.pow[i] * (long) function.applyAsInt(i));
            }
        }

        public int hash(int l, int r, boolean verbose) {
            long h = hash[r];
            if (l > 0) {
                h -= hash[l - 1];
                h *= hd.inv[l];
            }
            if (verbose) {
                h += hd.pow[r - l + 1];
            }
            return hd.mod.valueOf(h);
        }

    }

    static class Modular {
        int m;

        public Modular(int m) {
            this.m = m;
        }

        public Modular(long m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public Modular(double m) {
            this.m = (int) m;
            if (this.m != m) {
                throw new IllegalArgumentException();
            }
        }

        public int valueOf(int x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return x;
        }

        public int valueOf(long x) {
            x %= m;
            if (x < 0) {
                x += m;
            }
            return (int) x;
        }

        public int mul(int x, int y) {
            return valueOf((long) x * y);
        }

        public String toString() {
            return "mod " + m;
        }

    }

    static class HashData {
        public Modular mod;
        public int[] inv;
        public int[] pow;

        public HashData(int n, int p, int x) {
            this.mod = new Modular(p);
            n = Math.max(n, 1);
            inv = new int[n + 1];
            pow = new int[n + 1];
            inv[0] = 1;
            pow[0] = 1;
            int invX = new Power(mod).inverseByFermat(x);
            for (int i = 1; i <= n; i++) {
                inv[i] = mod.mul(inv[i - 1], invX);
                pow[i] = mod.mul(pow[i - 1], x);
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 20];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

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

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(10 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}

