Alice最近迷上了杀怪爬塔的游戏，在塔中有n层关卡，在通过第i层关卡后Alice会走上第i+1层。每个关卡中可能会获得女神的祝福或者遇到怪物。如果得到女神的祝福，Alice生命值会+1，如果遇到怪物Alice会被攻击并且生命值会-1，同时Alice也会把怪物解决掉。而Alice是一个硬核玩家，起初他的生命值为1，他想要最后生命值仍然为1。所以他问你，在第L层到第R层Alice能通过的关卡数最多是多少？
注意Alice可以从L~R的任意一层出发，期间任何时刻Alice生命值不能为0。
题目保证在1~n层中，无论Alice从哪一层开始挑战，他能通过的关卡数<=10。
第一行包含一个数字 n (1<=n<=100000) 表示有n层关卡。
第二行包含一个长度为n的只含有0或1的字符串来表示1~n层关卡，0表示这一层有怪物，1表示这一层会获得女神的祝福。
第三行包含一个数字 q (1<=q<=100000) 表示有q次询问。
接下来q行，每行包含两个数字L,R (1<=L<=R<=n) 表示询问L~R层。
对于q次询问，每行输出一个数字表示这次询问中Alice能通过的最多的关卡数。