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 static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

import java.util.*;

@SuppressWarnings("unused")
public class A2 {

	private final static boolean autoflush = false;

	private final static int MOD = (int) 1e9 + 7;
	private final static double eps = 1e-9;
	private final static int INF = (int) 1e9;

	public A2 () {
		int N = sc.nextInt();
		int K = sc.nextInt();

		long V = 0;
		for (int i : rep(N)) {
			long L = sc.nextInt();
			long R = sc.nextInt();
			V += R - L + 1;
		}

		int res = 0;
		while (V % K != 0) {
			++res;
			++V;
		}

		exit(res);
	}

	////////////////////////////////////////////////////////////////////////////////////
	private static int [] rep(int N) { return rep(0, N); }
	private static int [] rep(int S, int T) { int [] res = new int [max(T-S, 0)]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static int [] req(int S, int T) { return rep(S, T+1); }
	private static int [] sep(int N) { return sep(0, N); }
	private static int [] sep(int S, int T) { int [] res = new int [max(T-S, 0)]; for (int i = S; i < T; ++i) res[T-1-i] = i; return res; }
	private static int [] seq(int S, int T) { return sep(S, T+1); }
	private static int [] ccw (int [] D) {
		return new int [] { -D[1], D[0] };
	}
	private static int [] cw (int [] D) {
		return new int [] { D[1], -D[0] };
	}
	private static int digitSum(long N) {
		int res = 0;
		for (; N > 0; res += N % 10, N /= 10);
		return res;
	}
	private static <T extends Comparable<T>> T max(T x, T y) {
		return x.compareTo(y) > 0 ? x : y;
	}
	private static long mod(long x) {
		return ((x % MOD) + MOD) % MOD;
	}
	private static long mod(long x, long mod) {
		return ((x % mod) + mod) % mod;
	}
	private static String reverse (String S) {
		return new StringBuilder(S).reverse().toString();
	}
	private static char [][] toCharArrays(String [] S) {
		int N = S.length;
		char [][] res = new char [N][];
		for (int i : rep(N))
			res[i] = S[i].toCharArray();
		return res;
	}
	////////////////////////////////////////////////////////////////////////////////////
	private final static MyScanner sc = new MyScanner();
	private static class MyScanner {
		private String next() {
			newLine();
			return line[index++];
		}
		private char nextChar() {
			return next().charAt(0);
		}
		private int nextInt() {
			return Integer.parseInt(next());
		}
		private long nextLong() {
			return Long.parseLong(next());
		}
		private double nextDouble() {
			return Double.parseDouble(next());
		}
		private String nextLine() {
			line = null;
			return readLine();
		}
		private String [] nextStrings() {
			line = null;
			return readLine().split(" ");
		}
		private char [] nextChars() {
			return next ().toCharArray ();
		}
		private Integer [] nextInts() {
			String [] L = nextStrings();
			Integer [] res = new Integer [L.length];
			for (int i : rep(L.length))
				res[i] = Integer.parseInt(L[i]);
			return res;
		}
		private Long [] nextLongs() {
			String [] L = nextStrings();
			Long [] res = new Long [L.length];
			for (int i : rep(L.length))
				res[i] = Long.parseLong(L[i]);
			return res;
		}
		private Double [] nextDoubles() {
			String [] L = nextStrings();
			Double [] res = new Double [L.length];
			for (int i : rep(L.length))
				res[i] = Double.parseDouble(L[i]);
			return res;
		}
		private String [] next (int N) {
			String [] res = new String [N];
			for (int i : rep(N))
				res[i] = next();
			return res;
		}
		private Integer [] nextInt (int N) {
			Integer [] res = new Integer [N];
			for (int i : rep(N))
				res[i] = nextInt();
			return res;
		}
		private Long [] nextLong (int N) {
			Long [] res = new Long [N];
			for (int i : rep(N))
				res[i] = nextLong();
			return res;
		}
		private Double [] nextDouble (int N) {
			Double [] res = new Double [N];
			for (int i : rep(N))
				res[i] = nextDouble();
			return res;
		}
		private String [][] nextStrings (int N) {
			String [][] res = new String [N][];
			for (int i : rep(N))
				res[i] = nextStrings();
			return res;
		}
		private Integer [][] nextInts (int N) {
			Integer [][] res = new Integer [N][];
			for (int i : rep(N))
				res[i] = nextInts();
			return res;
		}
		private Long [][] nextLongs (int N) {
			Long [][] res = new Long [N][];
			for (int i : rep(N))
				res[i] = nextLongs();
			return res;
		}
		private Double [][] nextDoubles (int N) {
			Double [][] res = new Double [N][];
			for (int i : rep(N))
				res[i] = nextDoubles();
			return res;
		}
		//////////////////////////////////////////////
		private boolean eol() {
			return index == line.length;
		}
		private String readLine() {
			try {
				return r.readLine();
			} catch (Exception e) {
				throw new Error (e);
			}
		}
		private final java.io.BufferedReader r;
		private MyScanner () {
			this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in)));
		}
		private MyScanner (java.io.BufferedReader r) {
			try {
				this.r = r;
				while (!r.ready())
					Thread.sleep(1);
				start();
			} catch (Exception e) {
				throw new Error(e);
			}
		}
		private String [] line;
		private int index;
		private void newLine() {
			if (line == null || eol()) {
				line = readLine().split(" ");
				index = 0;
			}
		}
	}
	private static void print (Object o, Object... a) {
		printDelim(" ", o, a);
	}
	private static void cprint (Object o, Object... a) {
		printDelim("", o, a);
	}
	private static void printDelim (String delim, Object o, Object... a) {
		pw.println(build(delim, o, a));
	}
	private static void exit (Object o, Object... a) {
		print(o, a);
		exit();
	}
	private static void exit() {
		pw.close();
		System.out.flush();
		System.err.println("------------------");
		System.err.println("Time: " + ((millis() - t) / 1000.0));
		System.exit(0);
	}
	private static void NO() {
		throw new Error("NO!");
	}
	////////////////////////////////////////////////////////////////////////////////////
	private static String build (String delim, Object o, Object... a) {
		StringBuilder b = new StringBuilder();
		append(b, o, delim);
		for (Object p : a)
			append(b, p, delim);
		return b.toString().trim();
	}
	private static void append(StringBuilder b, Object o, String delim) {
		if (o.getClass().isArray()) {
			int L = java.lang.reflect.Array.getLength(o);
			for (int i : rep(L))
				append(b, java.lang.reflect.Array.get(o, i), delim);
		} else if (o instanceof Iterable<?>)
			for (Object p : (Iterable<?>)o)
				append(b, p, delim);
		else
			b.append(delim).append(o);
	}
	////////////////////////////////////////////////////////////////////////////////////
	private static void start() {
		t = millis();
	}
	private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out, autoflush);
	private static long t;
	private static long millis() {
		return System.currentTimeMillis();
	}
	private static void statics() {
		abs(0); valueOf(0); asList(new Object [0]); reverseOrder();
	}
	public static void main (String[] args) {
		new A2();
		exit();
	}
}
