Balance of parentheses

Given a sequence of opening and closing round, square, and curly brackets, your task is to write a program that determines if it's possible to insert numbers and arithmetic operation signs into this sequence to form a valid bracket expression.

Input

The input file contains between 1 and 10 lines. Each line consists of a sequence of brackets, with a maximum length of 255 characters.

Output

For each line in the input, output a single character, either 0 or 1, on a new line. The total number of output lines should match the number of input lines. Output 0 if the sequence can be transformed into a valid bracket expression, and 1 if it cannot.

Examples