小蓝原本拥有一套卡片，卡片上写的数字分别为 ，每个数字恰好一张。
后来，小蓝发现这套卡片中丢失了连续的 张。也就是说，存在一个正整数 ，使得写有数字 的卡片全部丢失，其中 。
丢失发生后，小蓝将剩下所有卡片上的数字相加，得到的总和为 。
现在，给定剩下卡片的数字之和 以及丢失的卡片张数 ，请你计算所有可能的原卡片总数 的总和。如果不存在任何符合条件的 ，则答案为 。同一个合法的 即使对应多种丢失情况，也只统计一次。
由于答案可能很大，你只需要给出满足条件的 的总和对 取模后的结果即可。
第一行包含一个正整数 ，表示询问的组数。
接下来 行，每行包含两个正整数 和 ，中间用一个空格隔开。
输出共 行，每行包含一个整数，表示对应询问中所有可能 的总和对 取模后的结果。
4 10 2 15670 27 20 3 35 1
11 579 0 8
对于第一组询问，。
因此可能的 为 和 ，答案为 。
对于 的评测用例，, , ；
对于所有评测用例，, , 。
