Background

要回家了，有一个小孩跑丢了

Description

在一个$n*n$的森林里

小孩用o表示，他的父母用i表示 父母可在上下左右的方向找孩子，问最快的时间是多少

Input

小孩用o表示，他的父母用i表示 父母可在上下左右的方向找孩子，问最快的时间是多少

Output

小孩用o表示，他的父母用i表示 父母可在上下左右的方向找孩子，问最快的时间是多少

Samples

2
iq
qo

2

Limitation

1s, 1024KiB for each test case. n <= 10