Another Meaning

Description

给出一段话$s$，和一个单词$t$，已知单词t别有深意，也就是说有两个意思，求$s$可能有多少种意思。答案对$1e9+7$取模。

Format

Input

一个整数$n$，表示数据组数
接下来就是$n$组$s$和$t$。

Output

$n$行，对应每组数据的答案

Example

Input

4
hehehe
hehe
woquxizaolehehe
woquxizaole
hehehehe
hehe
woyaoqugenbierenliaotianle
wanan

Output

3
2
5
1

Explanation

原字样表示取原意，加粗字体表示取深意
第一组：hehehe，hehehe，hehehe
第三组：hehehehe，hehehehe，hehehehe，hehehehe，hehehehe

Data

$strlen(t)\,<=\,strlen(s)\,<=\,100000，\,n\,<=\,10$ 仅有小写字符