说明

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

输入格式

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

输出格式

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

样例

3
2005 25
1855 12
2004 10000

2108
1904
43236