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: [*l*<sub class="lower-index">1</sub>; *r*<sub class="lower-index">1</sub>], [*l*<sub class="lower-index">2</sub>; *r*<sub class="lower-index">2</sub>], ..., [*l*<sub class="lower-index">*n*</sub>; *r*<sub class="lower-index">*n*</sub>]. 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 [*l*<sub class="lower-index">1</sub>; *r*<sub class="lower-index">1</sub>], [*l*<sub class="lower-index">2</sub>; *r*<sub class="lower-index">2</sub>], ..., [*l*<sub class="lower-index">*n*</sub>; *r*<sub class="lower-index">*n*</sub>] is the number of integers *x*, such that there is integer *j*, for which the following inequality holds, *l*<sub class="lower-index">*j*</sub> ≤ *x* ≤ *r*<sub class="lower-index">*j*</sub>.

Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by *k*.
The first line contains two integers *n* and *k* (1 ≤ *n*, *k* ≤ 10<sup class="upper-index">5</sup>). Each of the following *n* lines contain a segment as a pair of integers *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> ( - 10<sup class="upper-index">5</sup> ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>), separated by a space.

It is guaranteed that no two segments intersect. In other words, for any two integers *i*, *j* (1 ≤ *i* &lt; *j* ≤ *n*) the following inequality holds, *min*(*r*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*j*</sub>) &lt; *max*(*l*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*j*</sub>).
import sys
import math
from typing import Callable


def main() -> None:
	read: Callable[[], str] = sys.stdin.readline
	n, k = (int(i) for i in read().split())
	total_length_covered = 0
	for _ in range(n):
		l, r = (int(i) for i in read().split())
		total_length_covered += r - l + 1

	# The val we need to return is the difference between k and total_length_covered, because we need to take increase
	# the interval by that difference so that total_length_covered becomes divisible by k
	# But Since k can be smaller than the total_length_covered, we need to find the smallest multiple of k
	# that is greater than total_length_covered
	# We know that total_length_covered % k returns the remainder, which in other words is how is left after dividing
	# total_length_covered by k. Then the length remaining for total_length_covered to reach k would have to be
	#  k - (total_length_covered % k)
	# And to handle the case where total_length_covered % k, we need to % k the result since the number of steps in that
	# case would have to be 0
	print((k - (total_length_covered % k)) % k)



if __name__ == '__main__':
	main()