There are n + 1 cities, numbered from 0 to n. n roads connect these cities, the i-th road connects cities i - 1 and i (i ∈ [1, n]).

Each road has a direction. The directions are given by a string of n characters such that each character is either L or R. If the i-th character is L, it means that the i-th road initially goes from the city i to the city i - 1; otherwise it goes from the city i - 1 to the city i.

A traveler would like to visit as many cities of this country as possible. Initially, they will choose some city to start their journey from. Each day, the traveler must go from the city where they currently are to a neighboring city using one of the roads, and they can go along a road only if it is directed in the same direction they are going; i. e., if a road is directed from city i to the city i + 1, it is possible to travel from i to i + 1, but not from i + 1 to i. After the traveler moves to a neighboring city, all roads change their directions to the opposite ones. If the traveler cannot go from their current city to a neighboring city, their journey ends; it is also possible to end the journey whenever the traveler wants to.

The goal of the traveler is to visit as many different cities as possible (they can visit a city multiple times, but only the first visit is counted). For each city i, calculate the maximum number of different cities the traveler can visit during exactly one journey if they start in the city i. 

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases.

Each test case consists of two lines. The first line contains one integer n (1 ≤ n ≤ 3 ⋅ 10^5). The second line contains the string s consisting of exactly n characters, each character is either L or R.

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 10^5.

Output

For each test case, print n + 1 integers. The i-th integer should be equal to the maximum number of different cities the traveler can visit during one journey if this journey starts in the i-th city.

Example

Input


2
6
LRRRLL
3
LRL


Output


1 3 2 3 1 3 2
1 4 1 4
import java.io.*;
import java.util.*;

import javax.security.auth.x500.X500Principal;

import static java.util.Collections.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class cf {
    // clustering techniques: hierarchical, K-meansu
    private static final int MOD = (int) (1e9 + 7), MOD_FFT = 998244353;
    private static final Reader r = new Reader();
    private static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    private static final boolean thread = false;
    static final boolean HAS_TEST_CASES = true;
    static final int SCAN_LINE_LENGTH = 1010002;
    // static final Scanner sc = new Scanner(System.in);

    static int n, a[], e[][], vis[], m, b[];

    private static Vector<Integer> adj[], v = new Vector<>();
    private static Vector<pi> g;

    public static long[] enumPows(int a, int n, int mod) {
        a %= mod;
        long[] pows = new long[n + 1];
        pows[0] = 1;
        for (int i = 1; i <= n; i++)
            pows[i] = pows[i - 1] * a % mod;
        return pows;
    }

    // static long[] p2 = enumPows(2, 500007, MOD);
    // static ArrayList<Integer> prime = seive(25000);

    // static void solve() throws Exception {
    // long n = nl();
    // int ans = 0;
    // for (int i = 0; i <= n / 2020 + 1; i++) {
    // if ((n - (i * 2020)) % 2021 == 0 && n - (i * 2020) > -1)
    // ans = 1;
    // if ((n - (i * 2021)) % 2020 == 0 && n - (i * 2021) > -1)
    // ans = 1;
    // }

    // pn(ans == 1 ? "YES" : "NO");
    // }

    static void solve() throws Exception {
        int n = ni();
        char[] s = n().toCharArray();
        int[] dpl = new int[n + 1];
        int[] dpr = new int[n + 1];
        for (int i = 0; i < dpr.length; i++) {
            dpl[i] = 1;
            if (i == 0)
                continue;
            if (s[i - 1] == 'L') {
                if (i - 2 > -1 && s[i - 2] == 'R') {
                    dpl[i] += dpl[i - 2];
                }
                dpl[i]++;
            }
        }
        for (int i = dpr.length - 1; i >= 0; --i) {
            dpr[i] = 1;
            if (i == dpr.length - 1)
                continue;
            if (s[i] == 'R') {
                if (i + 1 <= s.length - 1 && s[i + 1] == 'L') {
                    dpr[i] += dpr[i + 2];
                }
                dpr[i]++;
            }
        }
        for (int i = 0; i < dpr.length; i++) {
            p(dpl[i] + dpr[i] - 1 + " ");
        }
        pn();
    }

    public static void main(final String[] args) throws Exception {
        if (!thread) {
            final int testcases = HAS_TEST_CASES ? ni() : 1;
            for (int i = 1; i <= testcases; i++) {
                // pni(i + " t");
                // out.print("Case #" + (i + 1) + ": ");
                try {
                    solve();
                } catch (final Exception e) {
                    // pni("idk Exception");
                    // e.printStackTrace(System.err);
                    // System.exit(0);
                    throw e;
                }
            }
            out.flush();
        }
        r.close();
        out.close();
    }

    private static boolean eq(long a, long b) {
        return Long.compare(a, b) == 0;
    }

    private static ArrayList<Integer> seive(int n) {
        ArrayList<Integer> p = new ArrayList<>();
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (f[i] == 1)
                continue;
            for (int j = i * i; j <= n && j < f.length; j += i) {
                f[j] = 1;
            }
        }
        for (int i = 2; i < f.length; i++) {
            if (f[i] == 0)
                p.add(i);
        }
        return p;
    }

    private static void s(int[] a) {
        Integer[] t = new Integer[a.length];
        for (int i = 0; i < t.length; i++) {
            t[i] = a[i];
        }
        sort(t);
        for (int i = 0; i < t.length; i++) {
            a[i] = t[i];
        }
    }

    int pow(int a, int b, int m) {
        int ans = 1;
        while (b != 0) {
            if ((b & 1) != 0)
                ans = (ans * a) % m;
            b /= 2;
            a = (a * a) % m;
        }
        return ans;
    }

    int modinv(int k) {
        return pow(k, MOD - 2, MOD);
    }

    private static void swap(final int i, final int j) {
        final int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static boolean isMulOverflow(final long A, final long B) {
        if (A == 0 || B == 0)
            return false;
        final long result = A * B;
        if (A == result / B)
            return true;
        return false;
    }

    private static int gcd(final int a, final int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    private static long gcd(final long a, final long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    private static class Pair<T, E> implements Comparable<Pair<T, E>> {
        T fir;
        E snd;

        Pair() {
        }

        Pair(final T x, final E y) {
            this.fir = x;
            this.snd = y;
        }

        @Override
        @SuppressWarnings("unchecked")
        public int compareTo(final Pair<T, E> o) {
            final int c = ((Comparable<T>) fir).compareTo(o.fir);
            return c != 0 ? c : ((Comparable<E>) snd).compareTo(o.snd);
        }

    }

    private static class pi implements Comparable<pi> {
        int fir, snd;

        pi() {
        }

        pi(final int a, final int b) {
            fir = a;
            snd = b;
        }

        public int compareTo(final pi o) {
            return fir == o.fir ? snd - o.snd : fir - o.fir;
        }

        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + fir;
            result = prime * result + snd;
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            pi other = (pi) obj;
            if (fir != other.fir)
                return false;
            if (snd != other.snd)
                return false;
            return true;
        }

    }

    private static <T> void checkV(final Vector<T> adj[], final int i) {
        adj[i] = adj[i] == null ? new Vector<>() : adj[i];
    }

    private static int[] na(final int n) throws Exception {
        final int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = ni();
        }
        return a;
    }

    private static int[] na1(final int n) throws Exception {
        final int[] a = new int[n + 1];
        for (int i = 1; i < a.length; i++) {
            a[i] = ni();
        }
        return a;
    }

    private static String n() throws IOException {
        return r.readToken();
    }

    private static String nln() throws IOException {
        return r.readLine();
    }

    private static int ni() throws IOException {
        return r.nextInt();
    }

    private static long nl() throws IOException {
        return r.nextLong();
    }

    private static double nd() throws IOException {
        return r.nextDouble();
    }

    private static void p(final Object o) {
        out.print(o);
    }

    private static void pn(final Object o) {
        out.println(o);
    }

    private static void pn() {
        out.println("");
    }

    private static void pi(final Object o) {
        out.print(o);
        out.flush();
    }

    private static void pni() {
        out.println("");
        out.flush();
    }

    private static void pni(final Object o) {
        out.println(o);
        out.flush();
    }

    private static class Reader {
        private final int BUFFER_SIZE = 1 << 17;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        // private StringTokenizer st;

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

        public Reader(final String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        final byte[] buf = new byte[SCAN_LINE_LENGTH];

        public String readLine() throws IOException {
            int cnt = 0;
            int c;
            o: while ((c = read()) != -1) {
                if (c == '\n')
                    if (cnt == 0)
                        continue o;
                    else
                        break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public String readToken() throws IOException {
            int cnt = 0;
            int c;
            o: while ((c = read()) != -1) {
                if (!(c >= 33 && c <= 126))
                    if (cnt == 0)
                        continue o;
                    else
                        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();
            final 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();
            final 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();
            final 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();
        }
    }

    // static {
    // if (thread)
    // new Thread(null, new Runnable() {
    // @Override
    // public void run() {
    // try {
    // final int testcases = HAS_TEST_CASES ? ni() : 1;
    // for (int i = 1; i <= testcases; i++) {
    // // out.print("Case #" + (i + 1) + ": ");
    // try {
    // solve();
    // } catch (final ArrayIndexOutOfBoundsException e) {
    // e.printStackTrace(System.err);
    // System.exit(-1);
    // } catch (final Exception e) {
    // pni("idk Exception in solve");
    // e.printStackTrace(System.err);
    // System.exit(-1);
    // }
    // }
    // out.flush();
    // } catch (final Throwable t) {
    // t.printStackTrace(System.err);
    // System.exit(-1);
    // }
    // }
    // }, "rec", (1L << 28)).start();
    // }

    @SuppressWarnings({ "unchecked", })
    private static <T> T deepCopy(final T old) {
        try {
            return (T) deepCopyObject(old);
        } catch (final IOException | ClassNotFoundException e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
        return null;
    }

    private static Object deepCopyObject(final Object oldObj) throws IOException, ClassNotFoundException {
        ObjectOutputStream oos = null;
        ObjectInputStream ois = null;
        try {
            final ByteArrayOutputStream bos = new ByteArrayOutputStream(); // A
            oos = new ObjectOutputStream(bos); // B
            // serialize and pass the object
            oos.writeObject(oldObj); // C
            oos.flush(); // D
            final ByteArrayInputStream bin = new ByteArrayInputStream(bos.toByteArray()); // E
            ois = new ObjectInputStream(bin); // F
            // return the new object
            return ois.readObject(); // G
        } catch (final ClassNotFoundException e) {
            pni("Exception in ObjectCloner = " + e);
            throw (e);
        } finally {
            oos.close();
            ois.close();
        }
    }

}