Time Limit: 500 MS    Memory Limit: 64000 K 


Description

Jibancanyang is falling in love with a girl. One day he wrote a love letter to the girl. The girl was very happy when she received the letter. But she want to know how much jibancanyang love her. In her opinion, the more times of her name written in the letter, the more jibancanyang love her. More precisely, the depth of jibancanyang's love is the number of her name in the letter.

Input

The first line of the input contains an integer T(1< = T< = 20) which means the number of test cases. Each test case contains two lines. First line is the letter (0 < length < 100000), which just contains lowercase letters and space. Second line is the girl name(0 < length < 100000), which just contains lowercase letters.

Output

For each test case, you should output one line, an integer corresponding to the depth of jibancanyang's love.

Sample Input

2 jymmd i reaaaaaaaaaaally love you jymmd ababa aba

Sample Output

1 2 Author mathon