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.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner3 in = new Scanner3(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskA {
    public void solve(int testNumber, Scanner3 in, PrintWriter out) {
        int n = in.nextInt();
        int k = in.nextInt();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            sum += r - l + 1;
        }
        int res = sum % k;
        if (res != 0)
            res = k - res;
        out.print(res);
    }
}

class Scanner3 {
    private byte[] buffer = new byte[8192];
    private int bufferLength;
    private int position;
    private BufferedInputStream inputStream;
    private boolean eof;

    public Scanner3(InputStream stream) {
        inputStream = new BufferedInputStream(stream);
    }

    private byte peek() {
        while ((bufferLength == 0 || position == bufferLength) && !eof) {
            try {
                bufferLength = inputStream.read(buffer);
                if (bufferLength == -1) {
                    eof = true;
                    return 0;
                }
                position = 0;
            } catch (IOException e) {
            }
        }
        return buffer[position];
    }

    public String next() {
        skipSpaces();
        if (eof)
            throw new InputMismatchException();
        StringBuilder res = new StringBuilder();
        while (true) {
            byte c = peek();
            if (spaceChar(c) || eof) {
                String s = res.toString();
                if (s.isEmpty() && eof)
                    throw new InputMismatchException();
                return s;
            } else {
                res.append((char) c);
                position++;
            }
        }
    }

    private void skipSpaces() {
        while (spaceChar(peek()) && !eof)
            position++;
    }

    private boolean spaceChar(byte c) {
        return c < 33;
    }

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

    }
