时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
贝贝因为挂科太多被迫退学，于是他回到了他的家乡放羊。
他有一块
面积大小的矩形土地，可以视为平面直角坐标系中的一个矩形，左下角为)
，右上角为)
。于是贝贝决定修建围栏和羊圈，二者必须都是矩形形状的。设围栏的左下角坐标为)
，右上角坐标为)
，羊圈的左下角坐标为)
，右上角坐标为)
。一个合法的修建方案需要满足以下条件：
1. 围栏、羊圈一定都需要是矩形的形状
2. 羊圈的面积至少为
，即
，
3. 围栏必须完全包裹着羊圈，即
且
4. 围栏的修建不能超出贝贝拥有土地的范围，即
且
因为贝贝是个笨比，所以他难以算出对于指定的
，合法的修建方案的数量，于是他便把这个问题交给了你。
他有一块
1. 围栏、羊圈一定都需要是矩形的形状
2. 羊圈的面积至少为
3. 围栏必须完全包裹着羊圈，即
4. 围栏的修建不能超出贝贝拥有土地的范围，即
因为贝贝是个笨比，所以他难以算出对于指定的
输入描述:
第一行，一个正整数，表示测试数据组数
对于每组测试数据，包含一行两个正整数
输出描述:
对于每个测试数据输出一行一个整数，表示合法的方案数量，答案对取模。
