C1909 [Contest #14]夕日的光辉

内存限制:256 MB 时间限制:1000 ms

题目描述

Wishes granted, and dreams fulfilled.
众喣均求天遂,蓦然回首,尽如人意。

A festival spans the day and reaches into the night: a celebration of sound.
绮怀萦绕苍穹,灯火辉煌,昼夜不息。这场喧闹的庆典,将于此刻拉开帷幕。

Join Kanae as you walk from song to song.
在 Kanae 的陪伴下,漫步于韵律与乐章的繁华街市。


Kanae 发现了一条写了 $n$ 个小写英文字母所组成的字符串 $str$ 的纸条,她想要在纸条上找到自己最喜欢的单词 "pink" 并裁剪下来。在裁剪之前,Kanae 要先找到 "pink" 这个子序列。

形式化地,我们定义一个字符串 $str$ 的子序列为在 $str$ 中选取一部分组成的字符串。例如当 $str =$abc时,$str$ 共有六个非空的子序列,分别是abcabbcacabc

现在将 $pos(i)$ 定义为 子序列 "pink" 的第 $i$ 个字符在原串 $str$ 中的位置,Kanae 剪下单词 "pink" 的花费定义为:

$\max\limits_{i \in {1,2,3}} {(pos(i+1)-pos(i)-1)}$

请你求出 Kanae 剪下单词 "pink" 的可能最大的花费。如果无法找到任何子序列 "pink" ,请你输出-1

输入格式

第一行有一个正整数 $T$ 代表一个文件有几组数据。

每个数据占 $2$ 行。

第 $1$ 行有 $1$ 个整数 $n$,表示字符串的长度。

第 $2$ 行有 $1$ 个长度为 $n$ 的字符串 $str$。

  • $1 \le T \le 10^5$

  • $4 \le n \le 10^6$

  • 所有数据的 $n$ 总和不超过 $10^6$

输出

共 $T$ 行。

第 $i$ 行代表第 $i$ 个数据的答案。

样例

样例输入 1

2 13 pahgiiadnqwnk 5 ipnki

样例输出 1

6 -1

提示