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.*;
import java.lang.*;
import java.math.BigInteger;


public class Main {
  
   // public static long[][]   dp = new long[5005][5005];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t,ca,i,j;
		
		String[] my;
		String line = br.readLine();
        my = line.split(" ");
        int n,m,k;
        n = Integer.parseInt(my[0]);
        m = Integer.parseInt(my[1]);
        int ans = 0;
        for(i=0;i<n;i++)
        {
            line = br.readLine();
            my = line.split(" ");
            t = Integer.parseInt(my[0]);
            ca = Integer.parseInt(my[1]);
            ans = ans + ca+1-t;
            ans = ans%m;
        }
        System.out.println((m-ans)%m);
        }
    
}
class ut implements Comparator<Team>{
    public int compare(Team first, Team other)
    {
          if(first.pr > other.pr)return -1;
        if(first.pr < other.pr)return 1;
        if(first.ti < other.ti)return -1;
        if(first.ti > other.ti)return 1;
        if(first.in < other.in)return -1;
        if(first.in > other.in)return 1;
        return 0;
    }
}
class Team implements Comparable{
    int pr,ti,in;
    public Team(int a, int b, int c)
    {
        pr = a;
        ti = b;
        in = c;
    }
    public String toString()
    {
        return pr + " " + ti + " " + in+ "\n";
    }
    public int compareTo(Object obj)
    {
        Team other = (Team)obj;
        if(pr > other.pr)return -1;
        if(pr < other.pr)return 1;
        if(ti < other.ti)return -1;
        if(ti > other.ti)return 1;
        if(in < other.in)return -1;
        if(in > other.in)return 1;
        return 0;
    }
}

