题目描述

一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,

现在问你：蜜蜂从蜂房M开始爬到蜂房$\red{N}$，$\red{M<N}$，有多少种爬行路线？

输入格式

输入数据的第一行是一个整数$\red{N<=10}$,表示测试实例的个数，然后是$\red{N}$ 行数据，每行包含两个整数$\red{a}$和$\red{b}$($\red{0<a<b<1000}$)。

输出格式

对于每个测试实例，请输出蜜蜂从蜂房$\red{a}$爬到蜂房$\red{b}$的可能路线数的$\red{对10000取模}$的结果，每个实例的输出占一行。

样例

输入样例

2
1 2
3 6

输出样例

1
3

数据范围与提示

$\red{0<a<b<1000}$.