在未来克隆技术越来越成熟，朱大神发现只有两个队友太少了，那就克隆一窝吧（foreverNo.1，foreverNo.2，…，foreverNo.n），但是克隆机器必须要朱大神控制，于是他请了after来帮忙观察克隆情况，after表示没睡醒于是就每次从克隆结果中随便找一个告诉朱大神。腹黑的朱大神马上就发现了after的消极怠工，于是故意在after数完后连问m次第i次数到第j次数之间有几种foreverNo.（问题可能重复但是一定满足i≤j，同时0<i,j≤n），after很快解决了这个问题，聪明的你能解决吗？

第一行包含一个一个正整数n (1 ≤ n ≤ 30000).，第二行有n个字符串，第三行只有一个正整数m (1 ≤ m ≤ 200000)，接下来m行每行包含两个正整数i、j （i≤j，同时0<i,j≤n）

对于每个问题输出有几种foreverNo.。