题目描述
在遥远的科丁大陆，有一个广为流传的神话：“凑齐七颗龙珠，就可以召唤神龙”。小科听到这个传说以后激动不已，下定决心一定要凑齐七颗龙珠，召唤神龙。从此，小科踏上了寻找七龙珠的艰辛路途，经过漫长而又艰苦的跋涉，小科终于找到了传说中的龙珠山，此情此景，让小科激动不已，小科仰天大笑：“哈哈， 我终于可以召唤神龙了”。然而就在他笑声结束的一刹那，一个白胡子老爷爷出现了，他对小科说道：“小伙子，不要高兴的太早，规则改了，你首先要破解我的谜题，才可以召唤神龙”，小科大惊失色，赶忙问道什么谜题？白胡子老爷爷手一挥，在小科的面前出现了N颗排成一行的龙珠，每个龙珠上都有一个数字D，白胡子老爷爷说道，你可以从这N个龙珠中，选出连续的一些龙珠，但是有三个要求，第一，只可以连续的选取，不可以跳着选。第二：你选出的所有龙珠上的数字之和必须是7的倍数。第三：选取的龙珠要尽可能的多。最后白胡子老爷爷说道：“看你辛辛苦苦来到这里也不容易，你只需要告诉我在满足条件的前提下，最多可以收集到多少颗龙珠就可以了”。听到这里小科已经傻了，显然作为一个勇士，解决这类问题不是小科的强项，现在小科希望你能帮他解决这个问题，如果你能成功的帮助他解决这个问题，他会把神龙借你骑几天。
输入格式
第一行，一个整数T，表示数据组数 T≤5
对于每组测试数据：
第一行，两个整数N和Q，表示数据长度及查询数量（1≤N,Q≤100000）
第二行，N个元素的序列A[1...N]（1≤A[i]≤1000）
接下来Q行，每行有两个整数L,R，表示查询的区间（1≤L≤R≤N）
输出格式
对于每次询问，输出一行，一个整数表示查询区间中满足条件的总的对数。
输入输出样列
输入样例1：
1
5 2
1 5 3 4 2
1 5
2 3
输出样例1：
6
0