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.math.*;
import java.lang.*;
import java.text.*; // java.text.DecimalFormat

public class Codeforces
{
  public StreamTokenizer st;
  public PrintWriter pw;
  public static final int modulo = 1000000009; 
  
  static class Point
  {
    public int x;
    public double y;
    Point(int _x, double _y)
    {
      x = _x;
      y = _y;
    }
  }
  
  void init(String in, String out) 
  {
    if (in.isEmpty())
      st = new StreamTokenizer(System.in);
    else
    {
      try
      {
        st = new StreamTokenizer(new BufferedReader(new FileReader(in)));
      }
      catch(FileNotFoundException e)
      {
        
      }
    }
    
    if (out.isEmpty())
      pw = new PrintWriter(System.out);
    else
    {
      try
      {
        pw = new PrintWriter(new FileWriter(out));
      }
      catch(IOException e)
      {
        
      }
    }
  }
  
  private void close()
  {
    pw.close();
  }
  
  private int nI()
  {
    try{
      st.nextToken();
    }
    catch(IOException e)
    {
      
    }
    return (int)st.nval;
  }
  
  private double nD()
  {
    try{
      st.nextToken();
    }
    catch(IOException e)
    {
      
    }
    return st.nval;
  }
  
  private String nS()
  {
    try{
      st.nextToken();
    }
    catch(IOException e)
    {
      
    }
    return st.sval;
  }
   
  private long nL()
  {
    try{
      st.nextToken();
    }
    catch(IOException e)
    {
      
    }
    return (long)st.nval;
  }
  
  public static void qSort(int[] A, int low, int high) {
    int i = low;                
    int j = high;
    int x = A[(low+high)/2];  
    do {
        while(A[i] < x) ++i;  
        while(A[j] > x) --j;  
        if(i <= j){           
            
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
       
            i++; j--;
        }
    } while(i < j);
    if(low < j) 
      qSort(A, low, j);
    if(i < high) 
      qSort(A, i, high);    
  }
  
  
  public static void main(String[] aslkdjlkgja) throws IOException
  {
   Codeforces z = new Codeforces();
   z.init("", "");
   
   int n = z.nI();
   int k = z.nI();
   int sum = 0;
   for (int i = 0 ; i < n; ++i)
   {
     int l = z.nI();
     int r =z.nI();
     sum += r-l + 1;
   }
   int t = 0;
   while(sum % k != 0)
   {
     ++t;
     ++sum;
   }
   System.out.println(t);
   
   z.close();
  }
   
  
  
  
}