The Wizard's Spellbook

Aldric the Wizard checks spell formulas written with nested brackets:~( )[ ] \{ \}~.
If brackets are mismatched or unclosed, the spell will backfire so spell is safe if each opener bracket has a matching closing bracket type in correct order such that expression is mathematically valid.

Your Task

Given a string containing only ~( )[ ] \{ \}~ output SAFE if all brackets are correctly matched and closed, otherwise print DANGEROUS

Input Specification

The first line contains ~T~ — the number of formulas to check. Each of the next ~T~ lines contains one formula string.

Output Specification

For each formula print SAFE or DANGEROUS

Sample Input

4
({[]})
([)]
{{{
()[]{}

Sample Output

SAFE
DANGEROUS
DANGEROUS
SAFE

Constraints

~1 <= T <= 100000~
~0 <= len(formula) <= 10\,000~
Formulas only contain ~( ) [ ] \{ \}~

Test cases available here!