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
//package Round_177;

import java.util.*;
import java.io.*;

import static java.lang.Math.*;

public class A {

    void solve () throws IOException {
        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 r = 0;
        while ((sum + r) % k != 0)
            r++;
        out.println(r);
    }

    String input = "";
    String output = "";

    FastScanner in;
    PrintWriter out;

    void run () {
        try {
            BufferedReader bf;
            if (input.length() == 0)
                bf = new BufferedReader(new InputStreamReader(
                        System.in));
            else
                bf = new BufferedReader(new FileReader(input));
            in = new FastScanner(bf);

            if (output.length() == 0)
                out = new PrintWriter(System.out);
            else
                out = new PrintWriter(new File(output));

            solve();

            out.close();
        } catch (Exception ex) {
            out.close();
            ex.printStackTrace();
        }
    }

    public static void main (String[] args) {
        new A().run();
    }

    class FastScanner {
        BufferedReader bf;
        StringTokenizer st;

        FastScanner(BufferedReader bf) {
            this.bf = bf;
        }

        String next () throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(bf.readLine());
            return st.nextToken();
        }

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

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

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

        int[] readIntArray (int n) throws IOException {
            int a[] = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] readLongArray (int n) throws IOException {
            long a[] = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}