Sparse Arrays

There are NN strings. Each string's length is no more than 2020 characters. There are also QQ queries. For each query, you are given a string, and you need to find out how many times this string occurred previously.

Input Format

The first line contains NN, the number of strings.
The next NN lines each contain a string.
The N+2N+2nd line contains QQ, the number of queries.
The following QQ lines each contain a query string.

Constraints

1≤N≤10001≤N≤1000 
1≤Q≤10001≤Q≤1000 
1≤1≤ lengthlength ofof anyany string≤20string≤20
Sample Input

4
aba
baba
aba
xzxb
3
aba
xzxb
ab
Sample Output

2
1
0
Explanation

Here, "aba" occurs twice, in the first and third string. The string "xzxb" occurs once in the fourth string, and "ab" does not occur at all.


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //System.out.println(n);
        String[] str1 = new String[n];
        str1[0] = sc.nextLine();
        for(int i=0;i<n;i++){
            str1[i] = sc.nextLine();
            //System.out.println(str1[i]);
        }
        int n2 = sc.nextInt();
        String[] str2 = new String[n2];
        str2[0] = sc.nextLine();
        for(int i=0;i<n2;i++){
            str2[i] = sc.nextLine();
        }
        for(int i=0;i<n2;i++){
            int count = 0;
            for(int j=0;j<n;j++){
                if(str2[i].equals(str1[j])){
                    count++;    
                }
            }
            System.out.println(count);
        }
    }
}