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
// Coded by register-Gen
// Date: 2021-01-29
// Special thanks to cf tool by xalanq

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define Grep(u) for(int i=head[u];i;i=e[i].nxt)

#define clear(a) memset(a,0,sizeof(a))
#define setinf(a) memset(a,0x3f,sizeof(a))
#define setninf(a) memset(a,0xcf,sizeof(a))
#define setneg1(a) memset(a,-1,sizeof(a))

#define pb push_back
#define mp std::make_pair
#define fi first
#define se second

#define yes {puts("YES");return;}
#define no {puts("NO");return;}

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
typedef std::vector<int> vi;
typedef std::vector<ll> vl;

const int N=5e5;
const int M=1e6;
const int P=998244353;
const int inf=0x3f3f3f3f;
const int ninf=0xcfcfcfcf;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ll llninf=0xcfcfcfcfcfcfcfcf;

struct Edge{int to,nxt;}e[M*2+10];int head[N+10],tote;
inline void addEdge(int u,int v){e[++tote].to=v;e[tote].nxt=head[u];head[u]=tote;}

//struct Edge{int to,nxt,w;}e[M*2+10];int head[N+10],tote;
//inline void addEdge(int u,int v,int w){e[++tote].to=v;e[tote].w=w;e[tote].nxt=head[u];head[u]=tote;}

#define gc() char(getchar())

template<typename T>inline T read(){
	T x=0;bool f=0;char c=gc();
	while(c<'0'||c>'9')f|=c=='-',c=gc();
	while(c>='0'&&c<='9')x=x*10+c-48,c=gc();
	return f?-x:x;
}
inline int ri(){return read<int>();}
inline ll rl(){return read<ll>();}
inline ui ru(){return read<ui>();}
inline ull rul(){return read<ull>();}
inline int rstr(char*& str){
	char c=gc();int res=0;
	while(c!='\n'&&c!='\r'&&c!=' ')str[++res]=c,c=gc();
	return res;
}
inline int rline(char*& str){
	char c=gc();int res=0;
	while(c!='\n'&&c!='\r')str[++res]=c,c=gc();
	return res;
}

#undef gc

template<typename T1,typename T2>inline void chkmax(T1& a,T2 b){if(a<b)a=b;}
template<typename T1,typename T2>inline void chkmin(T1& a,T2 b){if(a>b)a=b;}
template<typename T1,typename T2,typename T3>inline void chkmax(T1& a,T2& b,T3 c){if(c>a){b=a;a=c;}else if(c>b)b=c;}
template<typename T1,typename T2,typename T3>inline void chkmin(T1& a,T2& b,T3 c){if(c<a){b=a;a=c;}else if(c<b)b=c;}
template<typename T1,typename T2,typename T3>inline void add(T1& x,T2 y,T3 p=P){(x+=y)>=p&&(x-=p);}
template<typename T1,typename T2,typename T3>inline void mul(T1& x,T2 y,T3 p=P){x=1LL*x*y%P;}

template<typename T1,typename T2,typename T3>inline T1 qpow(T1 x,T2 y,T3 p=P){
	T1 res=T1(1);
	while(y){if(y&1)mul(res,x,p);y>>=1;mul(x,x,p);}
	return res;
}
template<typename T1,typename T2,typename T3>inline T1 qmul(T1 x,T2 y,T3 p=P){
	T1 res=T1(0);
	while(y){if(y&1)add(res,x,p);y>>=1;add(x,x,p);}
	return res;
}
template<typename T1,typename T2>inline T1 gcd(T1 x,T2 y){return !y?x:gcd(y,T2(x%y));}
template<typename T1,typename T2,typename T3>inline T1 exgcd(T1 a,T2 b,T3& x,T3& y){
	if(b==0)return x=T3(1),y=T3(0),void();
	T1 res=exgcd(b,a%b,x,y);
	T3 tmp=x;x=y;y=tmp-(a/b)*y;
	return res;
}

void solve();
int main(){
	int T;
//	T=1;
	T=ri();
	while(T--)solve();
	return 0;
}

struct Node{
	char l,r;
	bool ok;
};

Node t[N*4+10];
int n;
char str[N+10];

#define ls(x) (x<<1)
#define rs(x) (x<<1|1)

inline Node pushUp(Node L,Node R){
	Node res;
	res.l=L.l;
	res.r=R.r;
	res.ok=L.ok&&R.ok&&((L.r=='L'&&R.l=='R')||(L.r=='R'&&R.l=='L'));
	return res;
}

void build(int i,int l,int r){
	if(l==r){
		t[i].l=t[i].r=str[l];
		t[i].ok=1;
		return;
	}
	int mid=(l+r)>>1;
	build(ls(i),l,mid);
	build(rs(i),mid+1,r);
	t[i]=pushUp(t[ls(i)],t[rs(i)]);
}

Node query(int i,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr)return t[i];
	int mid=(l+r)>>1;
	if(qr<=mid)return query(ls(i),l,mid,ql,qr);
	if(ql>mid) return query(rs(i),mid+1,r,ql,qr);
	return pushUp(query(ls(i),l,mid,ql,qr),query(rs(i),mid+1,r,ql,qr));
}

#undef ls
#undef rs

int solve1(int pos){
	int l=pos+1,r=n,ans=pos;
	while(l<=r){
		int mid=(l+r)>>1;
		if(query(1,1,n,pos+1,mid).ok)ans=mid,l=mid+1;
		else r=mid-1;
//		printf("dee: %d %d %d\n",pos+1,mid,query(1,1,n,pos+1,mid).ok);
	}
	return ans-pos+1;
}

int solve2(int pos){
	int l=0,r=pos-1,ans=pos;
	while(l<=r){
		int mid=(l+r)>>1;
		if(query(1,1,n,mid+1,pos).ok)ans=mid,r=mid-1;
		else l=mid+1;
	}
	return pos-ans+1;
}

void solve(){
	rep(i,1,4*n)t[i].l=t[i].r=t[i].ok=0;
	rep(i,1,n)str[i]=0;
	n=ri();
	scanf("%s",str+1);
	build(1,1,n);
	rep(i,0,n){
		int ans=0;
		if(str[i+1]=='R')ans+=solve1(i);else ans++;
		if(str[i]=='L')ans+=solve2(i);else ans++;
		printf("%d ",ans-1);
	}
	puts("");
}