走地鸡地走
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

众所周知 SCUT 在一张平面直角坐标系上,里面生活着许多的散养走地鸡,它们很喜欢走来走去。有的走地鸡喜欢向左向右地走,有的走地鸡喜欢向上向下地走,还有的走地鸡喜欢转着圈地走。

走地鸡首领 SCUTkk 认为太多不同的走路方式不够整齐,于是它决定颁布《走地鸡走路法》,规定一下怎样才是“像走地鸡一样地走”:

  1. 在 SCUT 里,走地鸡每次只能向上下左右四个方向走一步。

  2. 在行走过程中不允许出现连续四次转向都是顺时针或逆时针的情况,因为走地鸡的脑容量比较小,这样会被绕晕。

  3. 在行走过程中不允许出现连续四次行走都向同一个方向的情况,因为走地鸡的耐心比较差,一直直走会很无聊。

  4. 在行走过程中不允许出现相邻两次行动方向相反的情况,因为走地鸡的体能比较差,大幅度变向会摔倒。

现在 SCUTkk 想聘请你成为走地鸡走路大法官,他会给你  只走地鸡的行走案例,让你判断每个案例是不是符合《走地鸡走路法》的规定。

注意:每个行走案例是一次完整的连续行走过程,不是循环的行走周期。

转向:每当相邻两次走路的方向不同,就称为发生了一次转向


输入描述:

第一行一个整数 t (1 \leq t \leq 10^{3}),代表行走案例的个数。接下来 n 行, 每行一个整数 n (1 \leq n \leq 10^{6})和一个字符串 s (s_i \in {L, R, U, D}),分别表示这个案例的行走长度和每次的行走方向,U 代表上,D代表下,L 代表左,R 代表右。数据保证 \sum n \leq 10^{6}

输出描述:

对于每个案例,如果符合《走地鸡走路法》则输出 YES ,否则输出 NO,中间以换行分隔。
示例1

输入

复制
5
1 U
5 ULLLL
6 UDUDUD
10 LLUURRDDLL
8 LURULURU

输出

复制
YES
NO
NO
NO
YES

说明

样例解释

第一组显然合法。

第二组违反了第三条规定,连续向左走了四次。

第三组违反了第四条规定,出现了上下折返。

第四组违反了第二条规定,连续顺时针转向了四次。

第五组是合法的。