We give the following inductive definition of a “regular brackets” sequence:*a*_{1}*a*_{2} … *a*_{n}, your goal is to find the length of the longest regular brackets sequence that is a subsequence of *s*. That is, you wish to find the largest *m* such that for indices *i*_{1}, *i*_{2}, …, *i*_{m} where 1 ≤ *i*_{1} < *i*_{2} < … < *i*_{m} ≤ *n*, *a*_{i}1*a*_{i}2 … *a*_{i}m is a regular brackets sequence.Given the initial sequence

- the empty sequence is a regular brackets sequence,
- if
*s*is a regular brackets sequence, then (*s*) and [*s*] are regular brackets sequences, and - if
*a*and*b*are regular brackets sequences, then*ab*is a regular brackets sequence. - no other sequence is a regular brackets sequence

`(), [], (()), ()[], ()[()]`

while the following character sequences are not:`(, ], )(, ([)], ([(]`

Given a brackets sequence of characters `([([]])]`

, the longest regular brackets subsequence is `[([])]`

.The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters

`(`

, `)`

, `[`

, and `]`

; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.提交代码