21681_Summation

Just as the problem title indicates, your task is to calculate the sum of several integers. Really simple! Right? No, not that simple actually, because many things are different from the usual summation, the operator, the operands, and so on. Please look into the following details:

First, instead of the usual addition scheme, you should do "No Carry Addition" here. That means we should add two integers according to the usual addition scheme, but ignore the carry everywhere in the addition. For example, suppose we would like to calculate the sum of 55 and 76 in the decimal system, then under the usual addition scheme, the result will be 131; while under the "No Carry Addition" scheme, the result is 21. These processes are illustrated below:

Second, the addition can be performed in any base from 2 to 16. For example, given two decimal numbers 55 and 76, then if we perform No Carry Addition in the decimal system, the sum of them is 21(decimal), while in the binary system, the binary representation of 55 and 76 are 110111 and 1001100 respectively, so the sum of them will be 1111011(binary) = 123(decimal).

Third, the operands are given in the format of integer segments instead of single integers. As we know, integer segment [x, y] represents consecutive integers starting from x and ending at y, and the sum of two segments [x₁, y₁] and [x₂, y₂] is equal to the sum of all the integers in each segment. (If one integer is inside both segments, then it should be calculated twice).

Now we can reach the conclusion of the problem statement: Given several integer segments and a base from 2 to 16, your task is to calculate the sum of them according to the "No Carry Addition" Scheme.

Input contains several test cases. The first line is a single integer, T ( 1 ≤ T ≤ 20 ), the number of test cases followed. For each test case, the first line is two integers, N, M, ( 1 ≤ N ≤ 100, 2 ≤ M ≤ 16 ), N is the number of integer segments, and M is the base in which the summation should be performed. And then N lines follow. Each line of them contains two 32-bit unsigned integers, x and y, representing the integer segment [x, y] (x and y are both in decimal representation, and x ≤ y).

For each test case, the output is one line containing a single 32-bit unsigned integer, representing the result in decimal format.

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

21
123
16