Description

求位数为B，各位数字之和为S，又是素数的个数。例如B=2，S=4的情况下，存在2个素数：13，31（注意该素数不能有前导0，即031不能算作3位素数）。

Input

第一行为T，表明测试数据组数。接下来一共T行分别为两个整数B和S，其中2<=B<=6，0<S。

Output

一共T行，每行对应一组B和S的解。

Sample

Input

3
2 4
4 2
5 31

Output

2
0
379