Little penguin Polo adores integer segments, that is, pairs of integers [l; r] (l ≤ r). 

He has a set that consists of n integer segments: [l1; r1], [l2; r2], ..., [ln; rn]. We know that no two segments of this set intersect. In one move Polo can either widen any segment of the set 1 unit to the left or 1 unit to the right, that is transform [l; r] to either segment [l - 1; r], or to segment [l; r + 1].

The value of a set of segments that consists of n segments [l1; r1], [l2; r2], ..., [ln; rn] is the number of integers x, such that there is integer j, for which the following inequality holds, lj ≤ x ≤ rj.

Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by k.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 105). Each of the following n lines contain a segment as a pair of integers li and ri ( - 105 ≤ li ≤ ri ≤ 105), separated by a space.

It is guaranteed that no two segments intersect. In other words, for any two integers i, j (1 ≤ i < j ≤ n) the following inequality holds, min(ri, rj) < max(li, lj).

Output

In a single line print a single integer — the answer to the problem.

Examples

Input

2 3
1 2
3 4


Output

2


Input

3 7
1 2
3 3
4 7


Output

0
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;



public class Sheet_A {
	
	public static boolean goodNumber(String num, int k) {
		
		for (char i = '0'; i <= '0' + k; i++)
			if(num.indexOf(i) == -1)
				return false;
		return true;
	}
	
	public static boolean isPrime(long n) {
		
		for (long i = n / 2; i >= 2; i--)
			if (n % i == 0)
				return false;
		return true;
	}
	
	public static boolean isCoPrime(long a, long b) {
		
		if (isPrime(a) && b % a != 0 || isPrime(b) && a % b != 0)
			return true;
		return false;
		
	}
	
	public static boolean isValid(int a1, int r1, int c1, int d1) {
		return (r1 - a1 <= 9 && r1 - a1 > 0 && c1 - a1 <= 9 && c1 - a1 > 0 && d1 - a1 <= 9 && d1 - a1 > 0 &&  a1 != d1 - a1 && a1 != c1 - a1 && a1 != r1 - a1 && r1 - a1 != d1 - a1 && r1 - a1 != c1 - a1 && d1 - a1 != c1 - a1);
	}
	
	
	
	

	public static void main(String[] args) {

		Scanner input = new Scanner(System.in);

		
		int n = input.nextInt();
		int k = input.nextInt();
		
		long count = 0;
		for (int i = 0; i < n; i++) {
			int first = input.nextInt();
			int second = input.nextInt();
			
			count += (second - first + 1);
			
		}
			
		System.out.println((count % k == 0) ? 0 : k - count % k);
		
		
		

	}
	
}

/*
int arr[] = new int[n];
for (int i = 0; i < n; i++)
arr[i] = input.nextInt();
*/

//Arrays.sort(arr);

/*for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
*/

/*
 * int n = input.nextInt();
	int t = input.nextInt();

	int k = (int) ((Math.pow(10 % t, n) % t) * -1 + 12);
			
	
	System.out.print(k + Math.pow(10, n));

	

 */