701591 - 阶乘数码

求n!中某个数码出现的次数。

Input

第一行为t(t≤10),表示数据组数。接下来t行,每行一个正整数n(n≤1000)和数码a。

Output

对于每组数据,输出一个整数,表示n!中a出现的次数。

Examples

Input

2
5 2
7 0

Output

1
2

Source

洛谷

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题