653. 求和B

正如本题标题所言，你的任务是计算一些整数的和，真的很简单，对吧？错，实际并非如此，因为这里面有很多跟普通的加法不同的地方，比如操作符、操作数啦等等。请仔细阅读下面的细节：
首先，你要抛开普通的加法规则，来进行不带进位的加法运算，那意味着我们必须依照普通加法规则把两个整数相加，但是要忽略掉每一个地方的进位。举个例子，假如我们要把十进制的 55 和 76 相加，使用普通的加法规则得到的结果为 131 ；然而使用“不带进位的加法”规则所得到的结果为 21 ，两种运算的过程如下图 1.2.1 和 1.2.2 所示。
 

其次，这种加法可以在 2 到 16 的任一种进制下运行，举例来说，给定两个十进制数 55 和 76 ，如果我们在十进制下进行这种不带进位的加法运算，他们的和为（ 21 ） 10 ，而在二进制下， 55 和 76 的二进制数分别表示为（ 110111 ） 2 和（ 1001100 ） 2 ，它们的和将为（ 1111011 ） 2 = （ 123 ） 10 。
最后一点，给定的操作数不是单一的整数，而是一个整数段，正如我们所知，整数段 [x,y] 表示从 x 开始，以 y 结束的连续的整数，两个整数段 [x1,y1] 、 [x2,y2] 的和等于每一个整数段中所有的整数的和。（如果一个整数在两个段里均存在，它将被计算两次。）
现在我们可以结束这个问题的阐述了：给定一些基于 2 到 16 进制的整数段，你的任务是依照无进位的加法规则计算它们的和。

【输入格式】

输入文件包含若干个测试数据，第一行是一个整数 T(1 ≤ T ≤ 20) ，表示下面有 T 组测试数据，对于每一组测试数据，第一行有两个整数， N 和 M ， (1 ≤ N ≤ 100 ， 2 ≤ M ≤ 16) ， N 表示整数段的个数， M 表示所求的和的进制数，接下来有 N 行，每一行包含两个 32 位无符号位的整数， x 和 y ，表示整数段 [x,y] （ x,y 均为十进制数，且 x ≤ y ）。

【输出格式】

对于每一组测试数据，输出只有一行，包含一个 32 位无符号位的整数，为计算结果的十进制表示。
 

【输入样例】

sumb.in

3
2 10
55 55
76 76
2 2
55 55
76 76
3 2
0 3
8 15
4 7