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.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.StringTokenizer;
 
public class Main{
 
    static class InputReader {
 
        final private int BUFFER_SIZE = 1 << 17;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public InputReader(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 String nextString() {
            StringBuilder sb = new StringBuilder("");
            byte c = next();
            while (c <= ' ') {
                c = next();
            }
            do {
                sb.append((char) c);
                c = next();
            } while (c > ' ');
            return sb.toString();
        }
 
        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++];
        }
    }
   
    public static void main(String arg[]) throws IOException {
   
     InputReader r=new InputReader(System.in);
       // BufferedReader r=new BufferedReader(new FileReader("input.txt"));
       // BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
   //     BufferedWriter wr=new BufferedWriter(new PrintWriter("output.txt"));
        PrintWriter p=new PrintWriter(System.out,false);

                   int n=r.nextInt();
                   int k=r.nextInt();
                   int count=0;
                   for(int i=0;i<n;i++)
                   {
                       count+=Math.abs(r.nextInt()-r.nextInt())+1;
                   }
                   
                   p.print(count%k==0?0:k-(count%k));
                p.flush();
}
}