ITES

q = [0] * 5000000

def solve(k, n):
    ss = 0
    cnt = 0
    prev = 1983
    front = 0
    rear = 0
    for i in xrange(n):
        num = prev % 10000 + 1
        prev = (prev * 214013 + 2531011) & 0xffffffff
        ss = ss + num
        q[rear] = num
        rear = rear + 1
        if rear == 5000000:
            rear = 0
        while ss >= k:
            if ss == k:
                cnt = cnt + 1
            ss = ss - q[front]
            front = front + 1
            if front == 5000000:
                front = 0
    return cnt

if __name__ == '__main__':
    c = input()
    while c > 0:
        c = c - 1
        k, n = (int(x) for x in raw_input().split())
        print solve(k, n)