众所周知，NTU Final PK 竞赛通常非常难。许多队伍在参加 NTU Final PK 竞赛时感到挫败。因此，我决定将第一题设计得尽可能“简单”（easy）。但是如何衡量一个问题有多简单呢？为了让我们的生活更轻松，我们只需考虑一个字符串有多“简单”。

在这里，我们引入一个合理的“简单度”（easiness）定义。一个字符串的简单度是满足由 $k$ 个 “easy” 拼接而成的字符串是该字符串的子序列的最大整数 $k$。例如，“eeaseyaesasyy”的简单度是 2。因为“easyeasy”是它的子序列，而“easyeasyeasy”则不是。

计算简单度似乎非常简单。现在给定一个仅由 'e'、'a'、's' 和 'y' 组成的字符串 $s$。请回答 $m$ 个询问。第 $i$ 个询问是一个区间 $[l_i, r_i]$，请计算 $s[l_i..r_i]$ 的简单度。

输入格式

第一行包含一个字符串 $s$。

第二行包含一个整数 $m$。

接下来的 $m$ 行，每行包含两个整数 $l_i, r_i$。

数据范围

• $1 \le |s| \le 10^5$
• $1 \le m \le 10^5$
• $1 \le l_i \le r_i \le |s|$
• $s$ 仅由 'e'、'a'、's' 和 'y' 组成

输出格式

对于每个询问，在一行中输出该子串的简单度。

样例

输入样例 1

easy
3
1 4
2 4
1 3

输出样例 1

1
0
0

输入样例 2

eeaseyaesasyy
4
1 13
2 12
2 10
3 11

输出样例 2

2
2
1
0