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.BufferedReader;
import java.io.*;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.Vector;


/**
 * Author: Luis Manuel Díaz Barón
 * Problem:
 * Online Judge:
 * Idea:
 * Fecha: 20/02/2013
 */

public class Main {

    static MyScanner sc;
    static MyWriter pw;
    static String filePath="/media/luismo/Trabajo/lmo.in";
    public static void main(String[] args) throws IOException {
        sc = new MyScanner(System.in);
        //sc = new MyScanner(new FileReader(filePath));
        pw = new MyWriter(System.out);

        //while(sc.canRead())
            SolveSingleProblem();

        pw.close();
    }

    public static void SolveSingleProblem() throws IOException{
        int n = sc.nextInt();
        int k = sc.nextInt();
        long cnt = 0;
        while (n-->0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            cnt += r-l+1;
        }

        if(cnt%k==0)
            pw.println(0);
        else{
            pw.println(k- cnt%k);
        }

    }


}


class MyScanner{
    BufferedReader br;
    StringTokenizer stk;
    public MyScanner(InputStream stream){
        this.br = new BufferedReader(new InputStreamReader(stream),72357);
        this.stk = new StringTokenizer("");
    }
    public MyScanner(FileReader fr){
        this.br = new BufferedReader(fr);
        this.stk = new StringTokenizer("");
    }
    public String next() throws IOException {
        while(!stk.hasMoreElements()){
            String line = br.readLine();
            if(line == null)
                return null;
            stk = new StringTokenizer(line);
        }
        return stk.nextToken();
    }
    public int nextInt()throws IOException{
        return Integer.parseInt(next());
    }
    public boolean canRead() throws IOException{
        return br.ready();
    }
}

class MyWriter{
    PrintWriter pw;
    public MyWriter(OutputStream out){
        this.pw = new PrintWriter(out);
    }
    public void print(Object obj){
        pw.print(obj.toString());
    }
    public void println(Object obj){
        pw.println(obj.toString());
    }
    public void printArr(int [] objects){
        for(int i =0;i<objects.length;i++){
            if(i!=0)
                print(" "+objects[i]);
            else print(objects[i]);
        }
        println("");
    }

    public void close() {
        pw.close();
    }
}