Background

attention is all you need.

Description

codeforces、atcoder、nowcoder、leetcoder、luogu、hydroj、domjudgeoj 是算法竞赛中的一些常见平台。

LargeRice16pro 天天游荡在这些平台之中，头都晕了，浏览器历史记录了 LargeRice16pro 访问这些平台的时间序列。

LargeRice16pro 把历史记录复制到本地后，格式出现了错误，记录之间的空格、换行没有了。

LargeRice16pro 想知道自己在 $[l_i,r_i]$ 这个时间区间浏览了多少次这些平台。请你帮帮他。

注：只要某平台名称在区间内出现一部分即可，例如：luogucodeforces，询问区间 $[3,7]$ 则算作浏览了 luogu 和 codeforces。

Format

Input

第一行一个字符串 $s(1\le |s|\le 10^7)$ 表示 LargeRice16pro 的浏览器历史记录。保证字符串仅由若干codeforces、atcoder、nowcoder、leetcoder、luogu、hydroj、domjudgeoj 按某种顺序拼接而成。

第二行一个正整数 $q(1\le q\le 10^6)$ 表示 LargeRice16pro 的询问次数。

接下来 $q$ 行，每行两个正整数 $l,r$ 表示询问的区间 $[l,r]$。

Output

输出共 $q$ 行，每行一个整数表示区间 $[l,r]$ 中出现的平台数量。

Samples

123 500

623

Limitation

1s, 1024KiB for each test case.