题目描述

在一个神秘的海底文明中，存在着一种神秘的水晶球，上面刻有三种不同的珍珠分别是$x,y,z$。每种配置最多有$s$ 个珍珠组成，且每种类型的珍珠数量不可以超过$t$ 。给定一个整数组数$n$，每组数据描述了其珍珠排列的规则，您的任务是找出有多少不同的珍珠排序方式可以满足给定的规则。

输入格式

第一行输入一个整数n，表示有n组珍珠排列规则。
接下来每组规则包含两个整数t和s，分别表示单个珍珠最多的数量和总珍珠数量。

输出格式

输出满足条件的不同珍珠排列方式的数量，以换行的格式输出。

样例数据

2
2 3
4 5

7
18

1
2000 1000

501501

样例解释

对于第一个样例，共有两组排列规则，第一组规则中单个珍珠最多可以是2个，在总数为3的情况下，满足条件的不同排列共有7种，分别是： 0 1 2， 0 2 1， 1 0 2，1 1 1， 1 2 0， 2 0 1，2 1 0 ， ；第二组规则中单个珍珠最多可以是4个，在总数为5的情况下，满足条件的不同排列共有18种。

数据范围

对于 $40\%$ 的数据，满足$0≤n≤10,$ $2≤T≤100$

对于 $100\%$的数据，满足$0≤n≤100,2≤T≤1000, 0≤S≤3×T$。