맹세

면접 대비

시간 제한1초메모리 제한128 MB

요약

주어진 단어를 원소 기호(한 글자 또는 두 글자)들의 연결로 분할할 수 있는지 DP로 판별합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 문자열
정답자: 아직 제출이 없습니다

문제

위대한 화학자 김선영은 굳은 맹세를 했다.

나는 오늘부터 원소 기호만으로 빈틈없이 이어 붙일 수 있는 단어만 말하겠다.

예를 들어 선영이는 "IAmCLaRa"를 말할 수 있다. 이 단어는 I(아이오딘), Am(아메리슘), C(탄소), La(란타넘), Ra(라듐)으로 나뉘기 때문이다. 또한 "InTeRnAtIONAl"도 In, Te, Rn, At, I, O, N, Al로 나뉘므로 말할 수 있다. 하지만 "collegiate", "programming", "contest"는 원소 기호의 연결로 나눌 수 없으므로 말할 수 없다.

단어가 주어졌을 때, 그 단어를 원소 기호들을 빈틈없이 이어 붙여 만들 수 있는지 판별하는 프로그램을 작성하시오. 대소문자는 구분하지 않는다.

다음은 이 문제에서 사용하는 주기율표이다.


H																	He
Li	Be											B	C	N	O	F	Ne
Na	Mg											Al	Si	P	S	Cl	Ar
K	Ca	Sc	Ti	V	Cr	Mn	Fe	Co	Ni	Cu	Zn	Ga	Ge	As	Se	Br	Kr
Rb	Sr	Y	Zr	Nb	Mo	Tc	Ru	Rh	Pd	Ag	Cd	In	Sn	Sb	Te	I	Xe
Cs	Ba	*	Hf	Ta	W	Re	Os	Ir	Pt	Au	Hg	Tl	Pb	Bi	Po	At	Rn
Fr	Ra	**	Rf	Db	Sg	Bh	Hs	Mt	Ds	Rg	Cn		Fl		Lv
* 란타넘족			La	Ce	Pr	Nd	Pm	Sm	Eu	Gd	Tb	Dy	Ho	Er	Tm	Yb	Lu
** 악티늄족			Ac	Th	Pa	U	Np	Pu	Am	Cm	Bk	Cf	Es	Fm	Md	No	Lr

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어지는 T개의 줄에는 각각 알파벳 소문자로만 이루어진 단어가 하나씩 주어진다. 각 단어의 길이는 1 이상 50,000 이하이다.

출력

각 단어마다 한 줄에 하나씩, 선영이가 발음할 수 있는 단어라면 YES를, 그렇지 않다면 NO를 출력한다.

예제7

예제 1

입력

4
international
collegiate
programming
contest

예상 출력

YES
NO
NO
NO

예제 2
입력
```
1
clara
```
예상 출력
```
YES
```
예제 3
입력
```
5
h
b
c
u
w
```
예상 출력
```
YES
YES
YES
YES
YES
```
예제 4
입력
```
4
a
d
j
q
```
예상 출력
```
NO
NO
NO
NO
```
예제 5
입력
```
1
sgd
```
예상 출력
```
YES
```
예제 6
입력
```
2
sgx
clz
```
예상 출력
```
NO
NO
```
예제 7
입력
```
3
no
nono
hydrogen
```
예상 출력
```
YES
YES
NO
```