牌桌上有 种不同的卡牌，第 种卡牌有 张。初始时，所有的卡牌均背面朝上，但不知道其确切的种类。你有两次翻牌机会，翻牌后，如果两张卡牌种类一致，那你就输了。两次翻牌同时进行（不存在根据翻开的第一张牌更改策略的情况）。 你不喜欢运气游戏，所以你可以通过手段随机预知 张卡牌后再进行游玩。 然而，预知很累！你想要知道，你至少需要预知多少张卡牌，才能保证你不会输。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入一个整数 代表卡牌种类数。第二行输入 个整数 代表每种卡牌数量。除此之外，保证每一组测试数据的卡牌总数之和不小于 ；单个测试文件的 之和不超过 。

输出描述:

对于每一组测试数据，如果没有必胜策略，直接输出 ；否则，在单独的一行上输出一个整数，代表你至少需要预知多少张卡牌，才能保证你不会输。