在聚会中，白茶听闻有一座千层之塔，塔内有 RTX 9090 Ti，强人工智能 AI 等一系列宝藏，率先到达塔底即可领取。于是白茶前去挑战。
《白茶与千层之塔》和《果冻与千层之塔》仅存在少量差别，你可以使用《果冻与千层之塔》的代码通过《白茶与千层之塔》。
在大断层，有一座无限高的塔，它的最低层是第 1 层。
每一个层都设置有只允许下行的遗物电梯。具体而言，第 k 层设置有一座直达第 k-1 层的电梯（若 k>1）和一座直达第 k-2 层的电梯（若 k>2）。特别地，如果 k \bmod 3 = 1，还额外设置有一座直达第 k-3 层的电梯（若 k>3），此处 \bmod 是取余运算。
假设你一开始位于第 a 层，想要前往第 1 层，你只允许乘坐前面所述的下行电梯，求前往的方案数。
输入
输入包含多组测试用例。
第一行包含一个整数 t \ (1 \leq t \leq 10)，表示你需要处理 t 组测试用例。
接下来 t 行每行一组测试用例，各包含两个用空格间隔的整数 a,b \ (2 \leq a \leq 20, b=1)，a 为开始所位于的楼层；b 为目标楼层，在本题中为固定值。
输出
对于每组测试用例，在单独的一行输出一个整数，表示答案。
在给定数据范围下，答案不会大于 20000。
样例
| 标准输入 复制文本 |
2 4 1 20 1 |
| 标准输出 复制文本 |
4 18750 |
提示
对于测试用例 1，四种方案如下：