#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std ;

const int maxNode = 400500 ; 
struct tireTree {
    int _cnt ;
    int tr[ maxNode ][ 30 ] ;
    int cnt[ maxNode ] ;
    tireTree ( ) {
        memset ( tr , 0 , sizeof( tr ) ) ;
        memset ( cnt , 0 , sizeof ( cnt ) ) ;
        _cnt = 1 ;
    }
    void insert ( char str[ ] ) {
        int len = strlen( str + 1 ) , cur = 1 ;
        for ( int i=1 ; i<=len ; ++i ) {
            int idx = str[ i ] - 'a' ;
            if ( !tr[ cur ][ idx ] )
                tr[ cur ][ idx ] = ++_cnt ;
            cur = tr[ cur ][ idx ] ;
        ++cnt[ cur ] ;
        }
    }
    int getPrefix ( char str[ ] ) {
        int len = strlen( str + 1 ) , cur = 1 ;
        for ( int i=1 ; i<=len ; ++i ) {
            int idx = str[ i ] - 'a' ;
            if ( !tr[ cur ][ idx ] )
                return 0 ;
            cur = tr[ cur ][ idx ] ;
        }
        return cnt[ cur ] ;
    }
} ;

tireTree tree ; 
char str [ 105 ] ;
int main ( ) {
    while ( gets ( str + 1 ) ) {
        if ( !strlen( str + 1 ) ) break ;
        tree.insert( str ) ;
    }
    while ( gets( str + 1 ) )
        printf ( "%d\n" , tree.getPrefix( str ) ) ;
    return 0 ; 
}

#include <cstdio>
#include <stack>
#include <cstring>

using namespace std ;
const int maxN = 50010 ; 

int In ( ) {
    int x = 0 , f = 1 ; char ch = getchar ( ) ;
    while ( ch < '0' || ch > '9' ) { if ( ch == '-')f = -1 ; ch = getchar ( ) ;}
    while ( ch >= '0' && ch <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + ch - '0' ; ch = getchar ( ) ;}
    return x * f ;  
}

stack <int> stk ; 
int arr[ maxN ] , ansl[ maxN ] , ansr[ maxN ] ;

int main ( ) {
    for ( int Kase = In ( ) , kase = 1 ; kase <= Kase ; ++kase ) {
        memset ( ansl , 0 , sizeof ( ansl ) ) ;
        memset ( ansr , 0 , sizeof ( ansr ) ) ;
        
        int N = In ( ) ; 
        for ( int i=1 ; i<=N ; ++i ) arr[ i ] = In ( ) ; 
        
        while(!stk.empty()) stk.pop() ;
        for ( int i=1 ; i<=N ; ++i ) {
            while ( !stk.empty() && arr[ stk.top() ] < arr[ i ] ) {
                ansl[ i ] = stk.top() ;
                stk.pop() ;
            }
            stk.push( i ) ;
        }
        
        while(!stk.empty()) stk.pop() ;
        for ( int i=N ; i>=1 ; --i ) {
            while ( !stk.empty() && arr[ stk.top() ] < arr[ i ] ) {
                ansr[ i ] = stk.top() ;
                stk.pop() ;
            }
            stk.push( i ) ;
        }
        printf ( "Case %d:\n" , kase ) ;
        for ( int i=1 ; i<=N ; ++i ) {
            printf ( "%d %d\n" , ansl[ i ] , ansr[ i ] ) ;
        }
    }
    return 0 ; 
} 

#include <string.h>
#include <stdio.h>
#include <iostream>
using namespace std ;
class bigInt
{
private :
    int num[10000], size;
    static const int maxN = 10000;
public :
    bigInt(char *ch)
    {
        size = strlen(ch);
        for(int i = 0; i < size; ++i)
        {
            if ( num[ i ] >= '0' && num[ i ] <= '9' ) num[i] = ch[size - i - 1] - '0';
        }
    } void Plus(bigInt o)
    {
        bool up = 0;
        size = size > o.size ? size : o.size ;
        for ( int i = 0 ; i < size ; ++i )
        {
            num[ i ] += o.num[ i ] + up ;
            up = false ;
            if ( num[ i ] >= 10 )
            {
                num[ i ] -= 10 ;
                up = true ;
            }
        }
        if ( up ) num[ size++ ] = 1;
    } void print()
    {
        for ( int i = size - 1 ; i >= 0 ; --i )
        {
            printf("%d", num[i]);
        }
    }
};
char str1[10000], str2[10000];
int main()
{
    int T ;
    cin >> T ;
    for(int k = 1; k <= T; ++k)
    {
        scanf("%s %s", &str1, &str2);
        bigInt A = bigInt ( str1 ) ;
        bigInt B = bigInt ( str2 ) ;
        A.Plus ( B ) ;
        printf("Case %d:\n", k);
        printf("%s + %s = ", str1, str2);
        A.print();
        printf("\n");
        if ( k != T ) printf("\n");
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std ;

const int maxN = 100100 ;
const int INF = 2147483647 ; 

int In ( ) {
    int x = 0 , f = 1 ; char ch = getchar ( ) ;
    while ( ch < '0' || ch > '9' ) { if ( ch == '-')f = -1 ; ch = getchar ( ) ;}
    while ( ch >= '0' && ch <= '9' ) { x = ( x << 1 ) + ( x << 3 ) + ch - '0' ; ch = getchar ( ) ;}
    return x * f ;  
}
int f[ maxN ] , arr[ maxN ] , sum[ maxN ] ; 
int main ( ) {
    int Kase = In ( ) ; 
    for ( int kase=1 ; kase<=Kase ; ++kase ) {
        int N = In ( ) ; 
        memset ( sum , 0 , sizeof ( sum ) ); memset ( f , 0 , sizeof ( f ) ); 
        for ( int i=1 ; i<=N ; ++i ) {
            sum[ i ] = sum[ i-1 ] + ( arr[ i ] = In ( ) ) ; 
        }
        for ( int i=1 ; i<=N ; ++i ) {
            f[ i ] = max ( f[ i - 1 ] + arr[ i ] , arr[ i ] ) ; 
        }
        int ans = -INF , indexOfMax , start = 0 ;
        for ( int i=1 ; i<=N ; ++i ) {
            if ( ans < f[ i ] ) indexOfMax = i , ans = f[ i ] ;
        }
        for ( int i=indexOfMax ; i>=0 ; --i ) {
            if ( sum[ indexOfMax ] - sum[ i ] == ans ) start = i ; 
        }
        printf ("Case %d:\n" , kase ) ; 
        cout << ans << ' ' << start + 1  << ' ' << indexOfMax << endl ; 
        if ( kase != Kase ) cout << endl ;
    }
    return 0 ;
}

#include <cstring>
#include <iostream>
#include <cstdio>
#include <map>

using namespace std ;

int main ( ) {
    
    int N ; 
    while ( cin >> N && N ) {
        map <string,int> mapColor ;
        for ( int i=1 ; i<=N ; ++i ) {
            string str ;
            cin >> str ;
            ++ mapColor[ str ] ;
        }
        map<string,int>::iterator it ; 
        int _cnt = 0 ;
        string strr ; 
        for ( it = mapColor.begin ( ) ; it != mapColor.end ( ) ; ++it ) {
            if ( it -> second > _cnt ) {
                _cnt = it -> second ;
                strr = it -> first ; 
            } 
        }
        cout << strr << endl ; 
    }
    return 0 ; 
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;

const int maxN = 10010 ;

struct Edge {
    int to , next , val ; 
}e[ maxN << 1 ] ;

long long head[ maxN ] , s[ maxN ] ;
int _cnt ; 
double ans ; 

void addEdge ( int _x , int _y , int _val ) {
    e[ ++_cnt ].to = _y ; 
    e[ _cnt ].next = head[ _x ] ; 
    head[ _x ] = _cnt ; 
    e[ _cnt ].val = _val ; 
}

void dfs ( const int x , const int fa , const int n ) {
    s[ x ] = 1 ;
    for ( int i=head[ x ] ; i ; i=e[i].next ) {
        if ( e[i].to != fa ) {
            dfs( e[i].to , x , n ) ;
            s[x] += s[e[i].to] ;
            ans += s[e[i].to] * ( n - s[e[i].to] ) * e[ i ].val ;
        }
    }
}
int main ( ) {
    int Kase ;
    scanf ("%d" ,&Kase ) ;
    for ( int k=1 ; k<=Kase ; ++k ) {
        int N ;
        scanf("%d",&N);
        memset(e,0,sizeof(e));
        memset(head,0,sizeof(head));
        memset(s,0,sizeof(s));
        _cnt = 0;
        ans = 0 ;
        for ( int i=1 ; i<N ; ++i ) {
            int x , y , val ; 
            scanf("%d%d%d" ,&x,&y,&val) ;
            addEdge ( ++x , ++y , val ) ;
            addEdge ( y , x , val ) ; 
        }
        dfs( 1 , 1 , N );
        printf("%.6lf\n",ans*2.0/N/(N-1));
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
 
int n,len,a[20],b[20],cnt;
 
int cmp(int a,int b){
    return a>b;
}
 
void dfs(int x,int posa,int sum,int posb){
    if(sum>n)
        return;
    if(sum == n){
        cnt++;
        for(int i = 0; i<posb; i++)
        {
            if(i)
                printf("+%d",b[i]);
            else
                printf("%d",b[i]);
        }
        printf("\n");
    }
    for(int i = posa; i<len; i++){
        b[posb] = a[i];
        dfs(a[i],i+1,sum+a[i],posb+1);
        while(i+1<len && a[i] == a[i+1]) i++;
    }
}
 
int main(){
    int i;
    while(~scanf("%d%d",&n,&len),n+len!=0){
        for(i = 0; i<len; i++)
            scanf("%d",&a[i]);
        sort(a,a+len,cmp);
        printf("Sums of %d:\n",n);
        cnt = 0;
        dfs(0,0,0,0);
        if(!cnt)printf("NONE\n");
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std ;

const int inf = 2147483647 ;
int wall[55][55][55],vis[55][55][55];
int xx[]={0,1,0,0,-1,0,0};
int yy[]={0,0,1,0,0,-1,0};
int zz[]={0,0,0,1,0,0,-1};

int ans ; 

struct Point {
    int x,y,z,t;
};

bool judge ( Point p ) {
    return wall[p.x][p.y][p.z]==0 && !vis[p.x][p.y][p.z] ;
}
void bfs ( int A,int B,int C,int lim ) {
    queue <Point>   Q;
    Q.push(Point{1,1,1,0});
    vis[1][1][1] = 1;
    while( !Q.empty() ) {
        Point tmp = Q.front();
        Q.pop() ;
        if ( tmp.x == A && tmp.y == B && tmp.z == C ) ans = min ( ans , tmp.t ) ;
        for ( int i=1 ; i<=6 ; ++i ) {
            int tx = tmp.x + xx[ i ] ;
            int ty = tmp.y + yy[ i ] ;
            int tz = tmp.z + zz[ i ] ;
            if ( judge(Point{tx,ty,tz,tmp.t+1}) ) {
                vis[tx][ty][tz] = 1 ;
                Q.push(Point{tx,ty,tz,tmp.t+1}) ;
            }
        }
    }
}

int main ( ) {
    int T ,lim;
    int A , B , C ;
    scanf("%d",&T) ;
    while ( T-- ) {
        memset(wall,-1,sizeof(wall));
        memset(vis,0,sizeof(wall));
        scanf("%d %d %d %d",&A,&B,&C,&lim);
        for ( int i=1 ; i<=A ; ++i ) {
            for ( int j=1 ; j<=B ; ++j ) {
                for ( int k=1 ; k<=C ; ++k ) {
                    scanf( "%d" ,&wall[i][j][k] ) ;
                }
            }
        }
        ans = inf ;
        bfs(A,B,C,lim);
        // cout << ans << endl ; 
        cout << ( ans <= lim ? ans : -1) << endl ; 
    }
    return 0 ;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>

using namespace std; 

int main ( ) {
    char str[ 10000 ] ;
    while(scanf("%s",str+1)==1){
        stack <char>    S ; 
        for( int i=1 ; str[i]!='\0' ; ++i ) {
            if ( str[i] == '(' ) S.push('(');
            else if( str[ i ] == ')' )S.pop();
            else {
                cout << S.size() << endl ;
                break ; 
            }
        }
    }
    return 0 ; 
}

#include <iostream>
#include <cstdio>

using namespace std;

double sum[54000];

int main()
{
    int n;
    double ans;
    ans = 0;
    sum[0] = 0;
    for(int i = 1; i <= 53000; i++)
    {
        ans += (1.0/i)*(1.0/i);    
        sum[i] = ans;
    }
    string s;
    while(cin>>s)
    {
        int len = s.length();
        n = 0;
        for(int i = 0; i < len; i++)
        {
            n = n*10+s[i]-'0';
            if(n > 120000)break;
        }
        if(n >= 110291)ans = 1.64493;
        else if(n >= 52447)ans = 1.64492;
        else ans = sum[n];
        printf("%.5lf\n", ans);
    }
    return 0;
}

#include <cstdio>
#include<iostream>
using namespace std ;


int main() {
    int m,n;
    while( cin >> m >> n ) printf("%.2lf\n" , (double)(1.0/m));
    return 0 ;
}

#include <bits/stdc++.h>

const int maxN = 1010 ; 
bool vis[maxN][maxN];
int map_[maxN][maxN];
int xx[] ={0,1,0,-1,0};
int yy[] ={0,0,1,0,-1};
bool flag ;
int n ,m ;

void dfs( int x , int y , int x2 , int y2 , int dir , int turns ) {
    if ( x == x2 && y == y2 && turns <= 2 ) {
        flag = true;
        return ;
    } 
    if ( flag || turns > 2 || (turns == 2 && (x != x2 && y != y2))) return ;
    for ( int i=1 ; i<=4 ; ++i ) {
        if ( x + xx[i]<1 || x + xx[i]>n || y + yy[i]<1 || y + yy[i]>m || vis[x + xx[i]][y + yy[i]] ) continue;
        if ( map_[x + xx[i]][y + yy[i]]==0 || ( x + xx[i]==x2 && y + yy[i]==y2 ) ) {
            vis[x + xx[i]][y + yy[i]] = true ;
            if ( !dir || dir == i ) 
                dfs (x + xx[i],y + yy[i],x2,y2,i,turns) ;
            else 
                dfs (x + xx[i],y + yy[i],x2,y2,i,turns+1) ;
            vis[x + xx[i]][y + yy[i]] = false ;
        }
    }
}
int main ( ) {
    int q ,x1,x2,y1,y2;;
    while(scanf("%d%d",&n,&m)!=EOF && n && m ) {
        for ( int i=1 ; i<=n ; ++i ) {
            for ( int j=1 ; j<=m ; ++j ) {
                scanf("%d",&map_[i][j]);
            }
        }
        scanf("%d",&q);
        while( q-- ) {
            memset(vis,0,sizeof(vis));
            flag = false ;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            if( map_[x1][y1] && map_[x2][y2] && map_[x1][y1]==map_[x2][y2] )
                dfs (x1,y1,x2,y2,0,0) ;
            printf(flag?"YES\n":"NO\n");
        }
    }
    return 0 ;
}

#include <bits/stdc++.h>

using namespace std ;
bool is_prime[]={0,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0},vis[100];
int arr[100];

void dfs( int dep , int n ) {
    if ( dep == n && is_prime[arr[1]+arr[dep]]) {
        for ( int i=1 ; i<n ; ++i ) {
            printf("%d ",arr[i]);
        }
        printf("%d\n",arr[n]);
    }else {
        for ( int i=2 ; i<=n ; ++i ) {
            if ( !vis[i] && is_prime[i+arr[dep]]) {
                vis[i] = true;
                arr[dep+1] = i ;
                dfs( dep + 1 , n ) ;
                vis[i]=false;
            }
        }
    }
}
int main(){
    int n , Kase = 0 ;
    while( cin >> n && n ) {
        printf("Case %d:\n",++Kase);
        arr[1] = 1;
        dfs(1 , n );
        printf("\n");
    }
    return 0 ; 
}

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            BigInteger p = BigInteger.ONE;
            for(int i=1;i<=n;i++)
                p=p.multiply(BigInteger.valueOf(i));
            System.out.println(p);
        }
    }
}

#include <bits/stdc++.h>

int main ( ) {
    int n , m ;
    double ans ; 
    std::cin >> n ;
    while ( n-- ) {
        ans = 0 ;
        std::cin >> m  ; 
        for ( int i=1; i<=m ; ++i ) {
            ans += log10(i) ;
        }
        std::cout << (int)ans+1 << std::endl ; 
    }
    return 0 ; 
}

#include <bits/stdc++.h>

using namespace std ;
char mp[110][110];
int n,m;
int xx[]={0,1,-1,0,-1,1,0,-1,1};
int yy[]={0,0,0,1,1,1,-1,-1,-1};

void dfs ( int x , int y ) {
    mp[x][y]='*';
    for ( int i=1 ; i<=8 ; ++i ) {
        if( mp[x+xx[i]][y+yy[i]]=='@' && x+xx[i]>0 && x+xx[i]<=n && y+yy[i]>0 && y+yy[i]<=m) {
            dfs(x+xx[i],y+yy[i]);
        }
    }
}
int main ( ) {
    
    while(cin >> n >> m  && n && m ) {
        getchar();
        for(int i=1 ; i<=n ; ++i ) {
            scanf("%s",mp[i]+1);
        }
        int ans = 0 ; 
        for(int i=1 ; i<=n ; ++i ) {
            for ( int j=1 ; j<=m ; ++j ) {
                if( mp[i][j]=='@' ) {
                    ans ++ ;
                    dfs(i,j);
                }
            }
        }
        cout << ans << endl ; 
    }
    return 0 ; 
}

#include <bits/stdc++.h>

using namespace std ;
int mp[10][10];
int pos_x[100],pos_y[100];
bool buc_h[10][10],buc_l[10][10],buc_blc[4][4][10];
bool flag;
void print ( ) {
    for ( int i=1 ; i<=9 ; ++i ) {
        for ( int j=1 ; j<9 ; ++j ) {
            cout << mp[i][j] << " " ;
        }
        cout << mp[i][9] << endl ; 
    }
}

void dfs( int dep , int tot ){
    if ( dep==tot+1 ){
        print();
        return ;
    }
    for ( int i=1 ; i<=9 ; ++i ) {
        if( !buc_h[pos_x[dep]][i] && !buc_l[pos_y[dep]][i]&&!buc_blc[(pos_x[dep]-1)/3+1][(pos_y[dep]-1)/3+1][i]) {
            mp[pos_x[dep]][pos_y[dep]] = i ;
            // print();
            buc_h[pos_x[dep]][i] = true;
            buc_l[pos_y[dep]][i] = true;
            buc_blc[(pos_x[dep]-1)/3+1][(pos_y[dep]-1)/3+1][i] = true;
            dfs( dep+1 , tot ) ; 
            buc_h[pos_x[dep]][i] = false;
            buc_l[pos_y[dep]][i] = false;
            buc_blc[(pos_x[dep]-1)/3+1][(pos_y[dep]-1)/3+1][i] = false;
        }
    }
}

int main () {
    int ____cnt = 0 ;
    while (true) {
        int _cnt = 0; char tmp ;
        memset(buc_h,false,sizeof(buc_h));
        memset(buc_l,false,sizeof(buc_l));
        memset(buc_blc,false,sizeof(buc_blc));
        flag = false;
        for( int i=1 ; i<=9 ; ++i ) {
            for ( int j=1 ; j<=9 ; ++j ) {
                if (!( cin >> tmp ) )goto End;
                else {
                    if(tmp=='?') {
                        mp[i][j] = 0;
                        pos_x[++_cnt] = i;
                        pos_y[_cnt] = j ;
                    } else {
                        buc_h[i][tmp-'0'] = true;
                        buc_l[j][tmp-'0']  =true;
                        buc_blc[(i-1)/3+1][(j-1)/3+1][tmp -'0'] = true;
                        mp[i][j] = tmp -'0';
                    }
                }
            }
        }
        if(____cnt++)printf("\n");
        dfs(1,_cnt);
    }
    End:
    return 0 ; 
}

/*
sample input
8 ? ? ? ? ? 6 5 ?
? ? ? ? ? 4 ? ? 7
? 5 6 ? ? 1 ? ? 3
5 ? ? 4 9 3 8 6 ?
? ? 8 2 7 ? 9 1 4
? 9 2 1 ? 8 ? 3 5
6 8 5 7 4 9 3 2 1
1 4 9 ? 3 ? 5 7 6
2 ? 7 5 ? ? ? ? ?
? ? 7 ? ? ? ? 2 6
6 5 ? 4 ? ? 1 8 ?
? 8 ? ? 2 ? ? ? 9
? 3 ? 6 1 8 ? 7 ?
? ? ? ? ? ? ? 6 ?
? 1 ? ? ? ? ? ? ?
? ? 8 ? ? 9 ? 1 ?
7 6 ? 3 ? ? 4 9 ?
? 9 5 ? ? ? ? ? 7

sample output
8 1 4 3 2 7 6 5 9
9 2 3 6 5 4 1 8 7
7 5 6 9 8 1 2 4 3
5 7 1 4 9 3 8 6 2
3 6 8 2 7 5 9 1 4
4 9 2 1 6 8 7 3 5
6 8 5 7 4 9 3 2 1
1 4 9 8 3 2 5 7 6
2 3 7 5 1 6 4 9 8

9 4 7 8 3 1 5 2 6
6 5 2 4 9 7 1 8 3
1 8 3 5 2 6 7 4 9
5 3 9 6 1 8 2 7 4
8 7 4 2 5 3 9 6 1
2 1 6 9 7 4 3 5 8
3 2 8 7 4 9 6 1 5
7 6 1 3 8 5 4 9 2
4 9 5 1 6 2 8 3 7
*/

#include <bits/stdc++.h>
using namespace std ;
int n ,m ,lim; 
bool flag; 
int mp[110][110];
int dx[]={0,0,1,0,-1};
int dy[]={0,1,0,-1,0};

void dfs ( int x , int y , int tarx , int tary , int dir , int turns ) {
    if ( turns > lim || flag ) return ;  
    if ( x==tarx && y==tary ){
        flag = true ; 
        return ; 
    }
    if(x!=tarx && y!=tary && turns==lim) return ; 
    for ( int i=1 ; i<=4 ; ++i ) {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if ( tx<1 || tx>n || ty<1 || ty > m || mp[tx][ty]=='*' ) continue ; 
        mp[tx][ty] = '*' ;
        if ( !dir || dir==i ) 
            dfs(tx,ty,tarx,tary,i,turns);
        else 
            dfs(tx,ty,tarx,tary,i,turns+1);
        mp[tx][ty] = '.' ; 
    }
}

int main ( ) {
    int T ,x1,x2,y1,y2; 
    scanf("%d",&T);
    while(T--){
        flag = false; 
        scanf("%d%d",&n,&m);
        for(int i=1 ; i<=n ; ++i ) 
            for(int j=1 ; j<=m ; ++j )
                scanf ( " %c" , &mp[i][j] ) ;
        scanf("%d%d%d%d%d",&lim,&x1,&y1,&x2,&y2);
        dfs(y1,x1,y2,x2,0,0) ;
        printf(flag?"yes\n":"no\n");
    }
}

#include <bits/stdc++.h>

using namespace std ;
const int maxNode = 100010 ; 
typedef long long LL ; 

struct tireTree {
private:
    static const int maxLen = 26 ; 
    int tr[ maxNode ][ maxLen ] ; 
    bool end[ maxNode ] ; 
    int count[ maxNode ] ; 
    int _cnt ; 
    
public :
    tireTree ( ) {
        _cnt = 1 ; 
        memset ( tr , 0 , sizeof ( tr ) ) ;
        memset ( end , false , sizeof ( end ) ) ;
    }
    void insert ( char str[ ] ) {
        int cur = 1 , len = strlen ( str + 1 ) ;
        for ( int i=1 ; i<=len ; ++i ) {
            int idx = str[ i ] - 'a' ; 
            if ( !tr[ cur ][ idx ] ) {
                tr[ cur ][ idx ] = ++_cnt ; 
            }
            cur = tr[ cur ][ idx ] ; 
        }
        end[ cur ] = true ; 
    }
    bool exist ( char str[ ] ) {
        int cur = 1 , len = strlen ( str + 1 ) ;
        for ( int i=1 ; i<=len ; ++i ) {
            int idx = str[ i ] - 'a' ; 
            if ( !tr[ cur ][ idx ] ) {
                return false ; 
            }
            cur = tr[ cur ][ idx ] ; 
        }
        return end[ cur ] ; 
    }
};
tireTree tree ; 
char str[50010][ 100 ] ;
int main ( ) {
    int cnt = 0 ; 
    freopen ( "input.in" , "r" , stdin ) ;
    while(scanf ( "%s" , str[++cnt] + 1 ) !=EOF ){
        tree.insert ( str[cnt] ) ; 
    }
    for ( int i=1 ; i<=cnt ; ++i ) {
        char tmp[100];
        int len = strlen(str[i]+1);
        for(int j=1 ; j<len ; ++j ) {
            tmp[j]=str[i][j];
            tmp[j+1]='\0';
            // cout << tree.exist(tmp) << endl ; 
            // cout << tree.exist(str[i]+j) << endl ; 
            if( tree.exist(tmp) && tree.exist(str[i]+j) ) {
                printf ("%s\n",str[i]+1);
                break;
            }
        }
    }
    fclose(stdin);
    return 0 ; 
}

#include <bits/stdc++.h>
using namespace std ;

const int maxN = 10100 ;
int a[maxN],f[maxN],b[maxN];

int main ( ) {
    int T , N ; 
    cin >> T ; 
    while ( T-- ) {
        cin >> N ; 
        for ( int i=1 ; i<=N ; ++i ) cin >> a[ i ] ;
        for ( int i=1 ; i<N ; ++i ) cin >> b[ i ] ;
        f[1]=a[1];f[2]=min( b[1] , a[1] + a[2] );
        for ( int i=3 ; i<=N ; ++i ) f[ i ] = min ( f[i-1] + a[i] , f[i-2] + b[i-1] ) ;
        if(f[N]/3600+8>12)printf("%02d:%02d:%02d pm\n", f[N]/3600+8-12, f[N]%3600/60,  f[N]%60);
        else printf("%02d:%02d:%02d am\n", f[N]/3600+8, f[N]%3600/60,  f[N]%60);
    }
    return 0 ;
}