There is a story that people who have the similar names will get along well with each other.So when finding a girl friend, you can

take this point into consideration ^_^. In MagicStar , people have a way to count the comparability between two names : the comparability between "kinfkong" and "kingkong" is 3 because they have the same prefix "kin", while it is 0 between the names "kinfkong" and "dingkong" which have not common prefix. Every person has an ID and a name. Dr.Longge want to count the sum of the comparabilities of q pairs of persons in the same set. Can you help him?

输入格式

In the first line there is n (1<n<=6000) indicating the number of people in MagicStar. The following n lines each containing an ID

and a name for a person. The length of the names is at least one but no more than 1000.IDs are in the range of 1 and n. No two IDs are the same. Next line is a number m. Then m sets follow.Each set starts with a number q in a line, meaning there are q queries in this set. Every query is made up of two IDs in a line. (m*q <= 10^6) .

输出格式

You task is to output m numbers, one in a line . The ith number is total comparabilities of the ith set.

样例输入

4 1 kingkong 2 dinfkong 3 kinfkong 4 kinfkonq 2 2 1 2 3 4 1 1 2

样例输出

7 0

#include<stdio.h> #include<string.h> char name[6001][1001]; char n1[1001],n2[1002]; int n,m,q; int main(){ int ans,i,j,k; scanf("%d",&n); while(n--){ scanf("%d",&i); scanf("%s",&name[i]); } scanf("%d",&m); while(m--){ scanf("%d",&q); ans=0; while(q--){ scanf("%d %d",&i,&j); for(k=0;name[i][k]!='\0'&&name[j][k]!='\0';k++){ if(name[i][k]!=name[j][k]) break; } ans+=k; } printf("%d\n",ans); } return 0; }