### Summation

Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem Description

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 [x1,y1] and [x2,y2] is euqal to the sum of all the integers in each segment. (If one integer is inside both segments, then it shoulde 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

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 intergers, 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).

#### Output

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

#### Sample Input

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

#### Sample Output

21
123
0