BRKTS - Brackets

no tags 

Your task is to determine if a sequence of opening and closing brackets is a valid expression. A valid expression is one where every opening bracket has a corresponding closing bracket.

Input

The input consists of several test cases. The first line of the input is an integer 0< n < 500. n lines follow, each one consisting of a sequence of brackets, which represents an expression.

Output

For each sequence in the input, print “:)” if the sequence is a valid expression, and “:(“ otherwise.

Example

Input:
4
{}
}}{{{{{
{{}{}}{}
{{}}}}}

Output:
:)
:(
:)
:(


Added by:Simón Santiago Soriano Pérez
Date:2011-05-12
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC GAWK MAWK BC C-CLANG C++ 4.3.2 CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET
Resource:https://docs.google.com/document/d/1WYMA9kda4g9zH7in5AsHjctKvkx8Nowc-V6FbMIpM_k/edit?hl=en&authkey=CMjAyJQO#