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.Scanner;

/**
 * User: Oleksiy Pylypenko
 * Date: 1/6/13
 * Time: 1:46 PM
 */
public class A {
    static boolean debug = !"true".equalsIgnoreCase(System.getProperty("ONLINE_JUDGE"));
    private Scanner in;
    private PrintWriter out;

    private void solve() throws IOException {
        int n = in.nextInt();
        int k = in.nextInt();

        long r = 0;
        for (int i = 0; i < n; i++) {
            long a = in.nextInt(), b = in.nextInt();
            r += b - a + 1;
        }
        long rest = r % k;
        if (rest == 0) rest = k;
        out.println(k - rest);
    }

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

    private void exec() {
        if (debug) {
            try {
                System.setIn(new FileInputStream(getClass().getName() + ".in"));
            } catch (FileNotFoundException e) {
                System.out.println(e);
                System.exit(1);
            }
        }
        in = new Scanner(new InputStreamReader(System.in));
        out = new PrintWriter(System.out, true);

        try {
            if (debug) {
                while (in.hasNext()) {
                    solve();
                }
            } else {
                solve();
            }
        } catch (IOException e) {
            if (debug) {
                System.out.println(e);
                System.exit(1);
            }
        } finally {
            out.close();
            in.close();
        }
    }

}
