奶牛庄严与奶牛白金转生到了异世界开始了新的冒险。一开始他们一穷二白，连生存都是个问题。异世界的神实在是看不下去了，于是派了一位使者前来帮助他们。 使者拿出了一个字符串 $S$，让他们俩分别选择起始点 $s_1,s_2$。定义**从 $s_1$ 位置开始的子字符串**与**从 $s_2$ 位置开始的子字符串**的最长公共前缀的长度为 $m$，那么使者将会给他们俩 $m$ 元钱作为新牛生的启动资金！ 牛牛们一脸疑惑，因为他们不会比较字符串，因此也算不出选定位置后能拿到多少钱，于是他们借助了次元量子通信技术与你通话。他们会问你很多很多个问题，每个问题会告诉你他们俩分别选择的位置，麻烦你告诉他们能拿到多少资金吧~

第一行一个正整数 $n$，表示字符串的长度。 第二行一个字符串 $S$，仅由小写字母组成。 第三行一个正整数 $q$，表示询问次数。 其后 $q$ 行，每行给定两个正整数 $s_1,s_2$，表示两头牛分别选择的位置。 $1\le n,q\le 100000$ $1\le s_1,s_2\le n$

输出 $q$ 行，每行输出一个整数，表示询问的答案。