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 sys
import math

def readints() :
    l = sys.stdin.readline()
    return map(int, l.split(' '))

def readstring() :
    l = sys.stdin.readline()[:-1]
    return l

def readint() :
    l = sys.stdin.readline()
    return int(l)

def clearchars(s, chars) :
    for c in chars :
        s = s.replace(c, '')
    return s

def gcd(a, b) :
    if (a < b ) :
        a, b = b, a
    if b == 0 :
        return a
    return gcd(b, a % b)

def hist(a) :
    h = {}
    for x in a :
        try : 
            h[x] += 1
        except KeyError :
            h[x] = 1
    return h

def lucky(n) :
    s = set(str(n))
    return all(map(lambda x: x in '47', s))    

def yslice(a, j) :
    return map(lambda x: x[j], a)

def dist2(a, b) :
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

def chain_len(a) :
    l = .0
    for d, e in zip(a, a[1:]) :
        l += dist2(d, e)
    return l

def is_prime(x) :
    if x == 1 :
        return False
    sq = int(x ** 0.5) 
    for i in [2] + range(3, sq + 1, 2) :
        if x % i == 0 :
            return False
    return True


digits = '0123456789'

def noe() :
    print "NO"
    exit(0)

def yese() :
    print "YES"
    exit(0)

n, k = readints()
s = 0
for i in range(n) :
    a, b = readints()
    s += b - a + 1

print (k - s % k ) % k
