题目描述

给你一个只包含小写字母的字符串 $s$（下标从 $1$ 开始）。
给你 $q$ 次询问，每次询问给你两个参数 $l,r$，问你子串 $s[l...r]$ 中有多少种字母出现次数为奇数。

输入格式

第一行一个字符串 $s$。
第二行一个整数 $q$。
接下来 $q$ 行，每行两个整数 $l,r$。

输出格式

输出 $q$ 行，表示答案。

输入输出样例 #1

输入 #1

abcab
3
1 2
1 3
2 5

输出 #1

2
3
2

说明/提示

$|s|\le 5\times 10^5,q\le 5\times 10^5$。