U623640 痴迷（Observance）

``` 街角的那个风铃 被风吹得咚咚叮叮 就像我摇坠的心 迎面而来的 就是你 ye 你完美弧度嘴 勾勒修长的身型 带着阳光的光晕 恨不得贴近 哦 对面那个男孩正步步走来 让我怎么能够不期待 是心动啊 糟糕 眼神躲不掉 相视就想要逃跑 我与你就好像 彗星与地球正在相撞 在这漫天粉色的季节 除了樱花和爱情 还有心动的你 转角遇见咖啡厅 遇见我心动的你 屋檐下摇曳风铃 叮叮咚咚好似我的心 哦 对面那个男孩正步步走来 让我怎么能够不期待 是心动啊 糟糕 眼神躲不掉 我害羞低头逃跑 我与你就好像 彗星与地球正在相撞 在这漫天粉色的季节 除了樱花和爱情 还有心动的你 ``` “喵喵市第一喵喵中学？” 初秋的微风拂过，撩起少年蓬松的棕发，粉红色的卫衣兜帽从宽大的校服背后垂落，平添几分俏皮，精致的五官匀称地铺在小巧的脸上，一对淡紫色的猫耳在头发里若隐若现，猫娘 9961 终于在高二的时候凭借自己的努力转入喵喵市重点中学——第一喵喵中学。 “嘿，我去，咋是你呀！” 突然，猫娘 9961 的肩膀上多了一只毛茸茸的小爪，9961 转头一看，竟然是他的发小猫娘 caizi！ “嗯~~~你好，caizi！我做到了！” “哎，意料之中的事，你天天卷，转来重点高中不是板上钉钉的事嘛！肯定一来就会把我这个竞赛，whk 都差得一塌糊涂的傻逼按在地板上摩擦！！！” 9961 转头一看，发现学校门口公示栏红榜最开头的赫然就是 caizi，而一旁学校代表人物“高一 NOI 金牌获得者——caizi”更是占了三分之二的表面。 “我的成功经历嘛？我没有什么天赋，四年级第一次参加比赛没有获得省一；我在信息学上每一天都很放松，训练时间小于等于 $14$ 小时；我以娱乐为主，每一天只做小于等于 $10$ 道题” 9961 读着版面上 caizi 的成功经历，再看着一旁还在对着自己说它有多差劲的 caizi，笑着摇了摇头“这就是天才嘛？我努力那么久，却仍触及不到它的尾巴”想着，它愤愤地抓住 caizi 那随着 caizi 贬低自己而逐渐下垂的尾巴。 “啊啊啊~~~好痛，别，别，别，我不说了，啊~”caizi 笑着惨叫着。 “你是哪个班的？我 2 班的。” “欸，这么巧啊！快走，我带你去班级看看。” caizi 的惨叫还飘在空气里，9961 就被它拉着，晕乎乎地朝教学楼走去。caizi 显然还沉浸在兴奋里，一边倒着走，一边手舞足蹈地跟 9961 比划着班上的趣事。9961 笑着听它讲，目光却不自觉地被校园里葱郁的树木和崭新的教学楼吸引。 就在他分神的一刹那，刚拐过教学楼的大厅转角，迎面便撞上了一个抱着厚厚一摞作业本、匆匆走来的身影。 “砰！”一声闷响，伴随着纸张散落的“哗啦”声。 “啊！对不起对不起！” 9961 下意识地道歉，赶紧蹲下身想去捡散落一地的本子。他的肩膀似乎还残留着刚才那一瞬间柔软触感，鼻尖萦绕着一丝清甜的、像是茉莉花一样的淡淡香气。 “没关系，是我走得太急了……” 一个温柔的声音在头顶响起。 9961 抬起头，瞬间撞见了一双清澈的琥珀色眼眸。午后的阳光透过大厅的玻璃窗，恰好洒在女孩身上，给她微卷的栗色长发镀上了一层柔和的光晕，那对同样毛茸茸的白色猫耳，因为这突如其来的碰撞而微微抖动了一下。她穿着合身的校服，裙摆随着她蹲下的动作轻轻摇曳。 时间仿佛在那一刻慢了下来。9961 感觉自己的心脏像是被什么东西猛地撞了一下，然后开始不争气地“咚咚”狂跳。他脑子里一片空白，之前 caizi 在耳边叽叽喳喳的声音仿佛瞬间被拉远、消失。他眼里只剩下这张近在咫尺的精致脸庞。 这就是……直击灵魂的感觉吗？9961 愣愣地想。他平时除了刷题和训练，几乎没什么和异性接触的经验，此刻更是完全宕机。他只知道，眼前这个女孩，好看得让他有点挪不开眼。 “喂！9961！你撞傻啦？” caizi 的大嗓门把他飘远的思绪拉了回来，也顺手捡起了几本作业，“班长大人，你没事吧？都怪这家伙走路不长眼睛！” “班长？” 9961 下意识地重复了一句，手忙脚乱地把捡起的本子递过去，动作僵硬得像是个生锈的机器人。他甚至不敢再看对方的眼睛，眼神飘忽地落在她的发梢，声音不自觉地变得又干又涩：“真…真对不起！” “没事，”女孩接过本子，露出一个灿烂的微笑，嘴角有两个浅浅的梨涡，“欢迎新同学。我是高二（2）班的班长，OI。” 她的笑容像是有魔力，9961感觉自己的脸颊有点发烫。他张了张嘴，平时还算灵光的脑子此刻却搜刮不出一句合适的话，最后只干巴巴地挤出一句：“我……我是新转来的，9961。” “知道啦，班主任提过你会今天来。” OI 抱着重新整理好的作业本，笑着点了点头，“快上课了，一起回教室吧？” 看着 OI 转身走在前面轻盈的背影，9961 还僵在原地。caizi 用胳膊肘使劲捅了他一下，压低声音坏笑：“嘿！回神了！眼睛都看直了！咋的，一见钟情啊？” 9961 猛地回过神，像是被说中了心事，耳根瞬间红透，条件反射地反驳：“胡……胡说什么！” 但目光却不受控制地，追随着前方那个身影，直到教室门口。他第一次觉得，转学来这个重点中学，或许除了梦想，还有了点别的、让他心跳加速的期待。 看着 OI 走进教室的背影，9961 还觉得脸颊有些发烫，直到上课铃响起，才被 caizi 一把拽进了高二（2）班的门。一天的课程在一种微妙的恍惚中度过，9961 的目光总是不自觉地飘向班长 OI 的方向，又在她似乎有所察觉时迅速缩回，假装认真盯着黑板。 放学后，caizi 熟门熟路地领着 9961 去宿舍楼。“我们运气不错，分到了传说中的‘三人间’，还有个空床位，正好给你！还有个家伙，你肯定合得来，也是个妙人儿。” caizi 挤眉弄眼地说。 推开宿舍门，只见一个戴着黑框眼镜、头发有些凌乱的猫娘正对着一台拆开一半的笔记本电脑，手指在键盘上飞快敲击，旁边还散落着几块电路板。听到开门声，她头也没抬，只是推了推眼镜，简短地打了声招呼：“来了？新室友？我是才子。” “嘿，科技狂魔才子！别鼓捣你那些宝贝了，来看看咱们的新室友，9961！” caizi 一把揽过 9961 的肩膀。 才子这才抬起头，目光透过镜片冷静地扫过 9961，点了点头：“嗯，caizi 提过你。欢迎。” 它的性格确实如 caizi 所说，带着理科生特有的简洁和专注，话不多，但似乎比 caizi 更沉稳一些。 简单的安置后，三个少年猫娘挤在并不宽敞的宿舍里，气氛很快活跃起来。主要是 caizi 在滔滔不绝，才子偶尔插几句精准的吐槽，而 9961 则有些心不在焉，脑海里还时不时浮现出 OI 带着梨涡的微笑。 “喂，9961，别发呆了！” caizi 显然注意到了他的走神，坏笑着用尾巴扫了扫他的脸，“来来来，长夜漫漫，我们来玩点刺激的——真心话大冒险！” 才子不置可否地挑了挑眉，但也没反对，算是默认加入了战局。 游戏开始，运气似乎偏偏要和 9961 作对。几轮下来，caizi 和才子你来我往，问题一个比一个刁钻，而轮到 9961 时，他抽到的纸条上赫然写着：“大冒险：跟你喜欢的人表白。” 9961 的脸唰地一下全红了，手一抖，纸条差点掉在地上。 “哇哦！！！” caizi 立刻爆发出巨大的起哄声，“喜欢的人，是谁是谁？是不是我们敬爱的班长 OI 大人？！我就知道！虽然她有许多个前任，但是根据小道消息，她最近单身，兄弟你包成功的！” 连才子也难得地露出了感兴趣的表情，镜片后的眼睛闪着光，淡淡地补刀：“根据行为学分析，他今天除了门口大妈和女班主任，只与班长 OI 有过近距离接触，且其瞳孔在相遇时有明显放大，心率估计飙升。目标锁定，概率99.8%。” “你们……！” 9961 羞得恨不得找个地缝钻进去。 “什么时候做？愿赌服输！” caizi 手舞足蹈的庆祝着，“不然你就得接受终极惩罚——去操场跑三圈并大喊‘我是傻逼’！” “我……我……”9961 犹豫着。 “欸我说，你不会真想在 OI 大人面前喊着‘我是傻逼’绕操场学鸭子跳三圈吧？” “不不不不，我做，我做，但，但，要正式，正式点吧……”9961 脸涨成了个大红苹果。 “阿~~~兄弟，我懂，到时候时机到了，叫上我俩就好了！时候不早了，21：57分了，睡觉，晚安各位”说着，已有微微的鼾声从 caizi 的床上传来，才子也去继续摆弄他的电路板了。 “我真的喜欢她嘛？额，应该是吧，我好想……”9961 摇摇头，把这些想法甩掉，开始思考如何实现这个大冒险了。

猫娘 9961 为 OI 姐姐买了一个礼物和一个插着相思叶的信封，准备写一封表白信，但它很体贴地考虑到 OI 姐姐更喜欢二进制，所以就把中文化成 $1$，英文化成 $0$，写了一封长为 $len$ 的信。 但是这个时候猫娘 9961 的好基友猫娘 caizi 出现把这封信复印了 $m$ 份，但这个打印机被科技狂魔**才子**爆改过，这个打印机在每一次打印时会把一个区间的英文先打印出来，中文后打印出来。 猫娘 9961 回到宿舍之后人傻了，他发现原件已经被猫娘 caizi 抢走全文朗读背诵了，只剩下 $m$ 份不知何意的复印件（虽说原本的信件也不知何意），猫娘 9961 只得重新写一份，但是为了惩罚猫娘 caizi，于是壁咚逼诱猫娘 caizi 告诉它 $m$ 份复印件有多少种完全不同的文章，猫娘 caizi 虽然暗爽，但是一想到它自己是坚定不移的 1，于是凭借全身的大神光环快速解决了这个问题，可猫娘 9961 依然疑惑，于是就找到了你。

第一行一个正整数 $T$，表示猫娘 caizi 到底背诵，复印了多少次表白信，即有多少组数据。 对于每一组数据，第一行两个正整数 $len,m$； 第二行是一个长为 $len$ 的字符串表示猫娘 9961 的表白信； 第 $3\sim 2+m$ 行是两个正整数 $l_i,r_i$，表示第 $i$ 次复印爆改区间 $l_i,r_i$。

输出共 $T$ 行，每一行一个整数表示完全不同的文章数量。

以第一组样例为例，原信封在打印出来分别是如下： 1. 101100 $\rightarrow$ 011100； 2. 101100 $\rightarrow$ 011100； 3. 101100 $\rightarrow$ 101100； 4. 101100 $\rightarrow$ 101100； 5. 101100 $\rightarrow$ 000111。 共有三种不同的文章：000111、011100 和 101100。 ## 数据范围 对于 $10\%$ 的数据，$len,m\leqslant10$。 对于 $30\%$ 的数据，$len,m\leqslant300$。 对于 $50\%$ 的数据，$len,m\leqslant1\times10^3$。 对于 $100\%$ 的数据，$T=5,1\leqslant len,m\leqslant2\times10^5,1\leqslant l_i\leqslant r_i\leqslant len$。