n=int(input()) l=[] for i in range (n): x,y=map(int,input().split()) arr=[x,y] l.append(arr) for i in l: j=0 if (i[0]%4==0 and i[0]%100!=0) or i[0]%400==0: j+=1 k=i[0] while True: if j==i[1]: break k+=1 if (k%4==0 and k%100!=0) or k%400==0: j+=1 print(k)