Problem: Grigory loves strings. Recently he found a metal strip on a loft. The strip had length n and consisted of letters "V" and "K". Unfortunately, rust has eaten some of the letters so that it's now impossible to understand which letter was written.

Grigory couldn't understand for a long time what these letters remind him of, so he became interested in the following question: if we put a letter "V" or "K" on each unreadable position, which values can the period of the resulting string be equal to?

A period of a string is such an integer d from 1 to the length of the string that if we put the string shifted by d positions to the right on itself, then all overlapping letters coincide. For example, 3 and 5 are periods of "VKKVK".

Input

There are several (at least one) test cases in the input. The first line contains single integer — the number of test cases.

There is an empty line before each test case. Each test case is described in two lines: the first line contains single integer n (1 ≤ n ≤ 5·105) — the length of the string, the second line contains the string of length n, consisting of letters "V", "K" and characters "?". The latter means the letter on its position is unreadable.

It is guaranteed that the sum of lengths among all test cases doesn't exceed 5·105.

For hacks you can only use tests with one test case.

Output

For each test case print two lines. In the first line print the number of possible periods after we replace each unreadable letter with "V" or "K". In the next line print all these values in increasing order.

Example

Input

3
 
5
V??VK
 
6
??????
 
4
?VK?


Output

2
3 5
6
1 2 3 4 5 6
3
2 3 4

Note

In the first test case from example we can obtain, for example, "VKKVK", which has periods 3 and 5.

In the second test case we can obtain "VVVVVV" which has all periods from 1 to 6.

In the third test case string "KVKV" has periods 2 and 4, and string "KVKK" has periods 3 and 4.

Solution (in JAVA):

Solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;
import java.util.StringTokenizer;
// 

public class e {
    static long MOD = 100000000;
    public static void main(String[] args) {
        FS in = new FS(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int t = in.nextInt();
        while(t-->0) new e().solve(in, out);

        out.close();
    }

    public void solve(FS in, PrintWriter out) {
        int n = in.nextInt();
        char[] arr = in.next().toCharArray();
        long[] v = new long[n+1];
        long[] k = new long[n+1];
        for(int i = 0; i < n; i++) if(arr[i] == 'V') v[i] = 1; else if(arr[i] == 'K') k[n-i-1] = 1;
        long[] mult = FFT.multiply(v, k);
        ArrayList<Integer> nums = new ArrayList<>();
        outer: for(int i = 1; i <= n; i++) {
            for(int j = i; j < n; j += i) if(mult[n-j-1] > 0 || mult[n+j-1] > 0) continue outer;
            nums.add(i);
        }
        out.println(nums.size());
        for(int a : nums) out.print(a + " ");
        out.println();
    }
        
    // SET maxk appropriately!!! ~log(maxn) //%
    static class FFT {

        static final int maxk = 20, maxn = (1 << maxk) + 1;
        // Init: wR, wI, rR, rI, aR, aI   to   new double[maxn] !!!
        //#
        static double[] wR = new double[maxn],
            wI = new double[maxn],
            rR = new double[maxn],
            rI = new double[maxn],
            aR = new double[maxn],
            aI = new double[maxn]; //$
        static int n, k, lastk = -1, dp[] = new int[maxn];

        static void fft(boolean inv) {
            if (lastk != k) {
                lastk = k;
                dp[0] = 0;
                for (int i = 1, g = -1; i < n; i++) {
                    if ((i & (i - 1)) == 0) {
                        g++;
                    }
                    dp[i] = dp[i ^ (1 << g)] ^ (1 << (k - 1 - g));
                }
                wR[1] = 1;
                wI[1] = 0;
                for (int t = 0; t < k - 1; t++) {
                    double a = Math.PI / n * (1 << (k - 1 - t));
                    double curR = Math.cos(a), curI = Math.sin(a);
                    int p2 = (1 << t), p3 = p2 * 2;
                    for (int j = p2, k = j * 2; j < p3; j++, k += 2) {
                        wR[k] = wR[j];
                        wI[k] = wI[j];
                        wR[k + 1] = wR[j] * curR - wI[j] * curI;
                        wI[k + 1] = wR[j] * curI + wI[j] * curR;
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                int d = dp[i];
                if (i < d) {
                    double tmp = aR[i];
                    aR[i] = aR[d];
                    aR[d] = tmp;
                    tmp = aI[i];
                    aI[i] = aI[d];
                    aI[d] = tmp;
                }
            }
            if (inv) {
                for (int i = 0; i < n; i++) {
                    aI[i] = -aI[i];
                }
            }
            for (int len = 1; len < n; len <<= 1) {
                for (int i = 0; i < n; i += len) {
                    int wit = len;
                    for (int it = 0, j = i + len; it < len; it++, i++, j++) {
                        double tmpR = aR[j] * wR[wit] - aI[j] * wI[wit];
                        double tmpI = aR[j] * wI[wit] + aI[j] * wR[wit];
                        wit++;
                        aR[j] = aR[i] - tmpR;
                        aI[j] = aI[i] - tmpI;
                        aR[i] += tmpR;
                        aI[i] += tmpI;
                    }
                }
            }
        }

        static long[] multiply(long[] a, long[] b) {
            int na = a.length, nb = b.length;
            for (k = 0, n = 1; n < na + nb - 1; n <<= 1, k++) {
            }
            for (int i = 0; i < n; ++i) {
                aR[i] = i < na ? a[i] : 0;
                aI[i] = i < nb ? b[i] : 0;
            }
            fft(false);
            aR[n] = aR[0];
            aI[n] = aI[0];
            double q = -1.0 / n / 4.0;
            for (int i = 0; i <= n - i; ++i) {
                double tmpR = aR[i] * aR[i] - aI[i] * aI[i];
                double tmpI = aR[i] * aI[i] * 2;
                tmpR -= aR[n - i] * aR[n - i] - aI[n - i] * aI[n - i];
                tmpI -= aR[n - i] * aI[n - i] * -2;
                aR[i] = -tmpI * q;
                aI[i] = tmpR * q;
                aR[n - i] = aR[i];
                aI[n - i] = -aI[i];
            }
            fft(true);
            long[] ans = new long[n = na + nb - 1]; // ONLY MOD IF NEEDED
            for (int i = 0; i < n; i++) {
                ans[i] = Math.round(aR[i]) % MOD;
            }
            return ans;
        }

        static void fft2(double[][] xr, double[][] xi, boolean inv) {
            n = xr[0].length;
            k = Integer.numberOfTrailingZeros(n);
            for (int i = 0; i < xr.length; i++) {
                for (int j = 0; j < n; j++) {
                    aR[j] = xr[i][j];
                    aI[j] = xi[i][j];
                }
                fft(inv);
                for (int j = 0; j < n; j++) {
                    xr[i][j] = aR[j] / (inv ? n : 1);
                    xi[i][j] = aI[j] / (inv ? -n : 1);
                }
            }
            n = xr.length;
            k = Integer.numberOfTrailingZeros(n);
            for (int j = 0; j < xr[0].length; j++) {
                for (int i = 0; i < n; i++) {
                    aR[i] = xr[i][j];
                    aI[i] = xi[i][j];
                }
                fft(inv);
                for (int i = 0; i < n; i++) {
                    xr[i][j] = aR[i] / (inv ? n : 1);
                    xi[i][j] = aI[i] / (inv ? -n : 1);
                }
            }
        }

        static long[][] multiply2(long[][] a, long[][] b) {
            int n1, n2;
            for (n1 = 1; n1 < a.length + b.length - 1; n1 <<= 1) {
            }
            for (n2 = 1; n2 < a[0].length + b[0].length - 1; n2 <<= 1) {
            }
            double[][] ar = new double[n1][n2], ai = new double[n1][n2];
            double[][] br = new double[n1][n2], bi = new double[n1][n2];
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[i].length; j++) {
                    ar[i][j] = a[i][j];
                }
            }
            for (int i = 0; i < b.length; i++) {
                for (int j = 0; j < b[i].length; j++) {
                    br[i][j] = b[i][j];
                }
            }
            fft2(ar, ai, false);
            fft2(br, bi, false);
            for (int i = 0; i < n1; i++) {
                for (int j = 0; j < n2; j++) {
                    double r1 = ar[i][j], r2 = br[i][j];
                    double i1 = ai[i][j], i2 = bi[i][j];
                    double real = r1 * r2 - i1 * i2;
                    ai[i][j] = i1 * r2 + i2 * r1;
                    ar[i][j] = real;
                }
            }
            fft2(ar, ai, true);
            long[][] result = new long[n1 = a.length + b.length - 1][n2 = a[0].length + b[0].length - 1];
            for (int i = 0; i < n1; i++) {
                for (int j = 0; j < n2; j++) {
                    result[i][j] = Math.round(ar[i][j]);
                }
            }
            return result;
        }
        //#

        static long[] multiplyPrecise(long[] a, long[] b) {
            long k = (long) (Math.sqrt(MOD));
            long[] a1 = new long[a.length], a2 = new long[a.length];
            long[] b1 = new long[b.length], b2 = new long[b.length];
            for (int i = 0; i < a.length; i++) {
                a1[i] = a[i] % k;
                a2[i] = a[i] / k;
            }
            for (int i = 0; i < b.length; i++) {
                b1[i] = b[i] % k;
                b2[i] = b[i] / k;
            }
            long[] r11 = multiply(a1, b1), r12 = multiply(a1, b2), r21 = multiply(a2, b1), r22 = multiply(a2, b2);
            long[] res = new long[r11.length];
            for (int i = 0; i < res.length; i++) {
                res[i] = (k * k * r22[i] + k * (r12[i] + r21[i]) + r11[i]) % MOD;
            }
            return res;
        }
        //$
        //#

        static long[] multiplyOr(long[] eq1, long[] eq2) {
            int n = Math.max(eq1.length, eq2.length);
            if ((n & (n - 1)) != 0) {
                n = Integer.highestOneBit(n) * 2;
            }
            eq1 = fftOr(eq1, n, false);
            eq2 = fftOr(eq2, n, false);
            for (int i = 0; i < eq1.length; i++) {
                eq1[i] *= eq2[i];
            }
            eq1 = fftOr(eq1, n, true);
            return eq1;
        }
        //$
        // To use: FFT both, product, iFFT (n is next power of 2)

        static long[] fftOr(long[] arr, int n, boolean invert) {
            long[] ans = Arrays.copyOf(arr, n);
            for (int b = 1; b < n; b <<= 1) {
                for (int i = 0; i < n; i++) {
                    if ((i & b) != 0) {
                        continue;
                    }
                    ans[i + b] += invert ? -ans[i] : ans[i];
                }
            }
            return ans;
        }

        static long[] fftXor(long[] arr, int n, boolean invert) {
            long[] ans = Arrays.copyOf(arr, n);
            for (int b = 1; b < n; b <<= 1) {
                for (int i = 0; i < n; i++) {
                    if ((i & b) != 0) {
                        continue;
                    }
                    long u = ans[i], v = ans[i + b];
                    ans[i] = u + v;
                    ans[i + b] = u - v;
                }
            }
            if (invert) {
                for (int i = 0; i < n; i++) {
                    ans[i] /= n;
                }
            }
            return ans;
        }
    }
        
    static class FS {

        BufferedReader in;
        StringTokenizer token;

        public FS(InputStream str) {
            in = new BufferedReader(new InputStreamReader(str));
        }

        public String next() {
            if (token == null || !token.hasMoreElements()) {
                try {
                    token = new StringTokenizer(in.readLine());
                } catch (IOException ex) {
                }
                return next();
            }
            return token.nextToken();
        }

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

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