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.InputStream;
import java.io.DataInputStream;

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

class TaskA {
    public void solve(int testNumber, FastReader in, PrintWriter out)
    {
        int n = in.nextInt();
        int k = in.nextInt();
        long sum = 0;
        for (int i = 0; i < n; i++)
        {
             int l = in.nextInt();
            int r = in.nextInt();
            sum += r-l+1;
        }
        int moves = 0;
        while(sum%k!=0)
        {
            moves++;
            sum++;
        }
        out.println(moves);
    }
}

class FastReader
{
    final private int BUFFER_SIZE = 1 << 17;

    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public FastReader(InputStream in) {
        din = new DataInputStream(in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }
    public byte next()
    {
        try {
            return read();
        } catch (Exception e) {
            throw new InputMismatchException();
        }
    }

    public int nextInt() {
        int ret = 0;
        byte c = next();
        while (c <= ' ')
            c = next();
        boolean neg = c == '-';
        if (neg)
            c = next();
        do {
            ret = (ret << 3) + (ret << 1) + c - '0';
            c = next();
        } while (c > ' ');
        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() {
        try {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        } catch (IOException e) {
            throw new InputMismatchException();
        }
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read()  {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }
}
