#P2309. Run time

Run time

11月22日,这一天发生了一件大事。

NQD同学下定决心要跑步!!!

没错,虽然不知道他能坚持几天,姑且先相信他。

他事情还比较稠,不光想跑步,还想知道他跑了多少步。最关键的是他还比较懒,自己不想查,你说咋能有这么懒得人呢。

因为NQD同学有良好的节奏感,他每秒恰好能跑一步。也就是说速度1步/秒。

然后聪明的NQD同学就想了一个办法。跑步的时候听音乐啊。

因为他播放器的每首歌的时间都是已知的,所以他只要每次记着是从那首歌开始跑步,那首歌听完停止。最后回来,计算一下歌的时间就能知道跑了多少步。

每首歌的时间都是该歌名字的所有字母的所有ascii码之和。

比如 XZY 这首歌对应的时间为88+90+89=267;

假设整个过程没有一切闲杂时间损耗,而且歌曲顺序播放!不会循环!,如果没有歌曲就停止跑步。 

Input

第一行输入一个数T,表示有T组测试数据;(1<=T<=10)

每组测试数据第1行输入两个数字n,q.(1<=n,q<=10000) 表示NQD学长的播放器中有n首歌,跑q次步。

第2行到n+1行每行输入一首歌的名字(名字的长度1<=len<=100)。

接下来q次查询,每次查询输入两个数字。l,r; 表示此次跑步听了播放器中第几首歌到第几首歌。

Output

每次查询,输出一个整数,

代表此次跑步的步数。

Sample Input

1
3 3
XZY
xzy
jiaruaiyoutianyi
1 1
1 2
2 3

Sample Output

267
630
2107

HINT

Source