#1531 단어 뽑아내기

24  1 s   128 MB  

Description

긴 단어속에서 또 다른 짧은 단어를 찾아내려고 한다.
striking 이라는 단어가 있을 때 이 단어에서 1, 2, 4, 7, 8번째 글자를 뽑아내면 sting이라는 단어가 되고 1, 2, 6, 7, 8번째 글자를 뽑아내도 역시 sting이라는 단어가 된다.

긴 단어와 짧은 단어가 주어질 때 긴 단어 안에 짧은 단어가 몇 개 존재하는지 판별하는 프로그램을 작성하라.

Input

먼저 테스트 케이스의 개수 T가 들어온다.
그 다음 T의 개수만큼 긴 단어 lword와 짧은단어 sword가 들어온다.
긴 단어의 크기는 1,000을 넘지 않고 작은 단어의 크기는 10을 넘지 않으며, 단어는 모두 대문자로만 이루어져 있다.
( 1 <= T <= 100 )

Output

각 테스트 케이스마다 긴 단어 안에 존재하는 짧은 단어의 개수를 출력한다.
만약 정답이 1,000,000,007 이상이라면 1,000,000,007로 나눈 나머지를 출력한다.

Sample Input

Sample Output

3
ABC AC
AABC AC
BCD EF
1
2
0

Source

From Arshuaz