解题思路

题意可抽象为：把 D 看作可行走的空地 .，隧道是由若干段连续的空地段（. 段）与障碍段（# 段）交替组成。 “轻松移动”就是在同一 . 段内左右走；一旦至少进行过一次轻松移动（即所在 . 段长度 ≥ 2），就可以“穿墙”越过紧邻在该段一侧的一整段 #，但穿墙需要从该 . 段的末端出发并且该端至少有两个连续的 .（正好是该段末尾的两个格），落点为墙另一侧的第一个 .。之后仍可继续走或继续穿下一堵墙。

因此，从包含 D 的那一段 .（记作区间 [L, R]）出发，有以下充要条件：

1. 若该段触达左边界（L==1）或右边界（R==n），直接走出即可，答案 YES。
2. 若该段长度为 1（R-L+1==1），无法进行任何“轻松移动”，也就不能启动穿墙，且不触边界时答案 NO。
3. 否则（该段长度 ≥ 2），可以选择向左或向右不断“穿一段墙 + 进入下一段 . 段”。

题目内容

多多在一个长为 $n$ 的横向隧道里，隧道每个位置用 $1$ 到 $n$ 的整数表示。

如果多多当前位置为 $x$ ，且他的左边(或右边)一个位置没有障碍物，则他可以轻松移动到 $x-1$ (或 $x+1$ )的位置。

多多还有一个"穿墙"的技能：如果他至少进行了一次轻松的移动,则他可以穿过原移动方向上的一段连续障碍物，并停留在这段障碍物的下一个位置。

形式化地说，如果在隧道区间 $[l,r]$ 内存在一段连续的障碍物，且 $l-2,l-1,r+1$(或 $l-1,r+1,r+2$) 位置无障碍物，则多多可以从 $l-2$ (或 $r+2$) 处出发穿墙并最终停留在 $r+1$ (或 $l-1$ )处。

给定隧道内障碍物的分布，问多多最终能否穿出隧道?

输入描述

第一行为一个整数 $T(1≤T≤10^6)$ ，表示接下来有 $T$ 组数据据。每组数据第一行为一个整数 $n(1≤n≤10^6)$ 表示表示隧道的长度，第二行为一个长度为 $n$ 的字符串，字符串由 "#","$D$" 组成，第 $i$ 个字符为 "#" 表示隧道的第 $i$ 个位置存在障碍物，'$.$' 表示空地(无障碍物)，'$D$' 即多多所在的初始位置。

数据保证 $\sum n≤10^6$，且每个字符串有且仅有一个字符串为 '$D$' 。

输出描述

若多多可以从初始位置到达位置 $0$ 或者 $n+1$ (即穿出隧道，这两个位置均无障碍物)，则输出"$YES$”，否则输出 $NO$”，每组数据对应一行输出。

样例1

输入

4
5
##D##
5
..D.#
7
#.#.D##
5
D####

输出

NO
YES
YES
YES

说明

第一组数据多多在第 $3$ 个位置动弹不得，无法穿出隧道、输出 $NO$ 。

第二组数据多多可以从左边一路走出随道，或者向右经过一次“轻松”的移动再穿墙而出。

第三组数据多多可以先向左走一步，再从右边穿墙而出。

第四组数据多多只能从左边走出隧道。