Since the finance department of MAKAUT has lots of bills to pass and funds to allocate for puja and freshers so there is a mess in Finance Officer's office. Although he has numbered all type of files from 0-9, all his files got jumbled up. Aaroti Di however arranged all of them to form a big integer n and presented it to Finance Office's office. But Finance officer wants to know how many files of a particular type q is there.
Help Aaroti Di to find out the count of a particular type.

Input

First line contains an integer t denoting the number of test cases.
Next 2t lines follow. Where first line shows the integer n of that test case and second line has the integer q, the file type queried for.

Output
Print the total number of files of the queried type in a new line.

Constraints

1 ≤ t ≤ 10^3
1 ≤ q ≤ 9
1 ≤ n ≤ 10^10

Sub Task
For 30 points

1 ≤ t ≤ 10^3
1 ≤ q ≤ 9
1 ≤ n ≤ 10^3

For 70 points

Orignal constraints

example
input
1
12
1
output
1

见题面

见题面