include//DFS版本
using namespace std;
string s;
vector<string>restore;
int mind=10000;
bool find(string sd)
{
for(int i=0;i<restore.size();i++){
if(sd==restore[i]) return true;
}
return false;
}
void bfs(int p,int sum)
{
//int i;
if(p==s.size()){
if(sum<mind) mind=sum;
}
else{
for(int i=p;i<s.size();i++){
string str=s.substr(p,i-p+1);
if(find(str)){
int q=i+1;
//cout<<str<<endl;
bfs(q,sum+1);
}
}
}
}
int main()
{
int t;cin>>t;
while(t--){
cin>>s;
restore.clear();
int n;cin>>n;
for(int i=0;i<n;i++){
string ssd;cin>>ssd;
restore.push_back(ssd);
}
bfs(0,0);
cout<<mind<<endl;
mind=10000;
}
}
EOJ 这个数学公式支持有点渣啊……