Background

Special for beginners, ^_^

Description

给出一个字符串 $S$ ，请在其中找到两个相同且不重叠的子串，输出相同且不重叠子串的最大长度。

Format

Input

本题包含多组数据。

每组数据第一行，一个 $n（1<n\le5000）$。

第二行一个长度为 $n$ 且只包含小写字母的字符串 $S$ 。

单个测试点的 $n$ 之和不超过 $10^6$。

Output

每行输出一个不重叠重复子串的最大长度。

Samples

2
ab
4
abab

0
2

Limitation

1s, 1024KiB for each test case.