Summation

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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: See Figure 1 and Figure 2. 



 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

Hint

Source

第9届中山大学程序设计竞赛预选赛