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.io.*;
import java.util.*;
import java.math.*;
import java.text.*;

public class Main {
	
	int n, k;
	
	void run(Input cin, PrintWriter out) throws Exception {
		n = cin.nextInt();
		k = cin.nextInt();
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			int a = cin.nextInt(), b = cin.nextInt();
			sum += b - a + 1;
		}
		if (sum > k) {
			if (sum % k == 0) sum = 0;
			else sum = k - sum % k;
		} else sum = k - sum;
		out.println(sum);
	}
	
	public static void main(String[] args) throws Exception {
		 PrintWriter out = new PrintWriter(System.out);
	     new Main().run(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
	     out.close();	     	     
	}
	
	static class Input {
	    BufferedReader in;
	    StringTokenizer st;

	    public Input(BufferedReader in) {
	        this.in = in;
	        eat("");
	    }

	    public Input(String s) {
	        this.in = new BufferedReader(new StringReader(s));
	    }

	    public void eat(String str) {
	        st = new StringTokenizer(str);
	    }

	    public String next() throws IOException {
	        while (!st.hasMoreTokens()) {
	            String line = in.readLine();
	            if (line == null) {
	                return null;
	            }
	            eat(line);
	        }
	        return st.nextToken();
	    }

	    public int nextInt() throws IOException {
	        return Integer.parseInt(next());
	    }

	    public long nextLong() throws IOException {
	        return Long.parseLong(next());
	    }

	    public double nextDouble() throws IOException {
	        return Double.parseDouble(next());
	    }
	}
}