Space Alignment

Time limit1sMemory limit2048 MB

Summary

Given a file whose indentation mixes tabs and spaces, find the smallest tab width that makes every line's indentation a consistent multiple of one unit, or report -1.

Level: Easy3 of 10
Topics: Brute force, Implementation, Math
Solved: No attempts yet

Problem

You are working with a few other programmers on a coding project. You discover that some people have been indenting code with tabs while others used spaces, all within the same file. Nobody noticed anything wrong.

You want to replace the tabs with spaces so that the file has consistent indentation. Indentation is consistent when, for every line at nesting depth $k$ , $k \ge 0$ , the first non-whitespace character is preceded by exactly $k \cdot i$ spaces, where $i>0$ .

Is it possible to replace each tab with a fixed number of spaces so that the file has consistent indentation?

Input

The first line contains a single integer $n$ ( $2 \le n \le 100$ ), the number of lines of code. Each of the next $n$ lines contains a string of the characters 's' (a space) and/or 't' (a tab), followed by a single { or }. Each line has at most 1000 characters.

The first line is always a single {, and the last line is always a single }. The braces always match: if you look only at the brace characters, you can repeatedly remove a substring {} until nothing is left.

Output

Output a single integer: the smallest positive number of spaces to replace each tab with so that the indentation is consistent, or -1 if no such number exists.

Examples1

Example 1
Input
```
10
{
ss{
sts{
tt}
t}
t{
ss}
}
{
}
```
Expected output
```
2
```