题目描述

小明出生在一个闰年，他想知道什么时候可以过生日，你能告诉他吗？ 给你一个正整数$\red{Y}$，表示起始年份，和一个正整数$\red{N}$，你的任务是告诉小明从$\red{Y}$年开始第$\red{N}$个闰年是哪一年。 注意：如果$\red{Y}$就是闰年，那么第一个闰年就是$\red{Y}$。

输入格式

输入的第一行为一个整数$\red{T}$，表示测试数据的组数。 每一组输入包含两个正整数$\red{Y}$和$\red{N}$（$\red{1<=N<=10000}$）。

输出格式

对于每组输入，输出从$\red Y$年开始第$\red{N}$个闰年是哪一年。

样例

输入样例

3
2005 25
1855 12
2004 10000

输出样例

2108
1904
43236