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 java.math.*;
import java.lang.*;

public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        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 String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            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 nextLong() {
            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 double nextDouble() {
            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, nextInt());
                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, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

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

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new Main(), "Main", 1 << 27).start();
    }

    static class Pair {
        int f;
        int s;
        int p;
        PrintWriter w;

        // int t;

        Pair(int f, int s) {
            // Pair(int f,int s, PrintWriter w){
            this.f = f;
            this.s = s;
            // this.p = p;
            // this.w = w;
            // this.t = t;

        }

        public static Comparator<Pair> wc = new Comparator<Pair>() {
            public int compare(Pair e1, Pair e2) {

                // 1 for swap
                if (Math.abs(e1.f) - Math.abs(e2.f) != 0) {
                    // e1.w.println("**"+e1.f+" "+e2.f);
                    return (Math.abs(e1.f) - Math.abs(e2.f));
                } else {
                    // e1.w.println("##"+e1.f+" "+e2.f);
                    return (Math.abs(e1.s) - Math.abs(e2.s));
                }

            }
        };
    }

    public static ArrayList<Integer> sieve(int N) {
        int i, j, flag;

        ArrayList<Integer> p = new ArrayList<Integer>();

        for (i = 1; i < N; i++) {

            if (i == 1 || i == 0)
                continue;

            flag = 1;

            for (j = 2; j <= i / 2; ++j) {
                if (i % j == 0) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {
                p.add(i);
            }
        }
        return p;
    }

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

    //// recursive dfs
    public static int dfs(int s, ArrayList<Integer>[] g, long[] dist, boolean[] v, PrintWriter w, int p) {
        v[s] = true;
        int ans = 1;
        // int n = dist.length - 1;
        int t = g[s].size();
        // int max = 1;
        for (int i = 0; i < t; i++) {
            int x = g[s].get(i);
            if (!v[x]) {
                // dist[x] = dist[s] + 1;
                ans = Math.min(ans, dfs(x, g, dist, v, w, s));
            } else if (x != p) {
                // w.println("* " + s + " " + x + " " + p);
                ans = 0;
            }
        }
        // max = Math.max(max,(n-p));
        return ans;
    }

    //// iterative BFS
    public static int bfs(int s, ArrayList<Integer>[] g, long[] dist, boolean[] b, PrintWriter w, int p) {
        b[s] = true;
        int siz = 1;
        // dist--;
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        while (q.size() != 0) {
            int i = q.poll();
            Iterator<Integer> it = g[i].listIterator();
            int z = 0;
            while (it.hasNext()) {
                z = it.next();
                if (!b[z]) {
                    b[z] = true;
                    // dist--;
                    dist[z] = dist[i] + 1;
                    // siz++;
                    q.add(z);
                } else if (z != p) {
                    siz = 0;
                }
            }

        }
        return siz;
    }

    public static int lower(int key, int[] a) {
        int l = 0;
        int r = a.length - 1;
        int res = 0;

        while (l <= r) {
            int mid = (l + r) / 2;

            if (a[mid] <= key) {
                l = mid + 1;
                res = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return res;
    }

    public static long power(long x, long y, long m) {
        if (y == 0)
            return 1;

        long p = power(x, y / 2, m) % m;
        p = (p * p) % m;

        if (y % 2 == 0)
            return p;
        else
            return (x * p) % m;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////////////
    // code here
    int[] parent;
    int[] dist;
    int[] height;
    boolean[] vis;
    ArrayList<Integer>[] g;
    int[] c;

    public void run() {

        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
        int defaultValue = 0;
        int mod = 1000000007;
        int oo = (int) 1e9;

        int test = 1;
        test = sc.nextInt();
        while (test-- > 0) {
            int n = sc.nextInt();
            char[] a = sc.next().toCharArray();
            g = new ArrayList[n + 1];
            for (int i = 0; i <= n; i++) {
                g[i] = new ArrayList<Integer>();
            }
            parent = new int[n + 1];
            dist = new int[n + 1];
            vis = new boolean[n + 1];
            Arrays.fill(dist, 1);
            for (int i = 0; i <= n; i++) {
                if (i > 0) {
                    if (a[i - 1] == 'L') {
                        if (i - 2 <= -1 || a[i - 2] == 'L') {

                            dist[i]++;
                        }
                        // if (i - 2 > -1 && a[i - 2] == 'R') {
                        // g[i].add(i - 2);

                        // }
                    }
                }
                if (i < n) {
                    if (a[i] == 'R') {
                        dist[i]++;
                        if (i + 1 < n && a[i + 1] == 'L') {
                            g[i].add(i + 2);

                        }
                    }
                }

            }
            for (int i = 0; i <= n; i++) {
                if (!vis[i]) {
                    // w.println("*" + i);
                    sol(i, -1);
                }
            }
            Arrays.fill(vis, false);
            for (int i = 0; i <= n; i++) {
                if (!vis[i]) {
                    // w.println("*" + i);
                    sol2(i);
                }
            }
            for (int i = 0; i <= n; i++) {
                w.print(dist[i] + " ");
            }
            w.println("");

        }

        w.flush();
        w.close();

    }

    public int sol(int s, int p) {
        vis[s] = true;
        parent[s] = p;
        for (int x : g[s]) {
            if (!vis[x]) {
                dist[s] += sol(x, s);
            }
        }
        return dist[s];
    }

    public void sol2(int s) {
        vis[s] = true;
        for (int x : g[s]) {
            if (!vis[x]) {
                dist[x] += dist[s] - dist[x];
                sol2(x);
            }
        }
    }

}
