Problem: You are given n strings s1, s2, ..., sn consisting of characters 0 and 1. m operations are performed, on each of them you concatenate two existing strings into a new one. On the i-th operation the concatenation saisbi is saved into a new string sn + i (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer k such that all possible strings consisting of 0 and 1 of length k (there are 2k such strings) are substrings of the new string. If there is no such k, print 0.

Input

The first line contains single integer n (1 ≤ n ≤ 100) — the number of strings. The next n lines contain strings s1, s2, ..., sn (1 ≤ |si| ≤ 100), one per line. The total length of strings is not greater than 100.

The next line contains single integer m (1 ≤ m ≤ 100) — the number of operations. m lines follow, each of them contains two integers ai abd bi (1 ≤ ai, bi ≤ n + i - 1) — the number of strings that are concatenated to form sn + i.

Output

Print m lines, each should contain one integer — the answer to the question after the corresponding operation.

Example

Input

5
01
10
101
11111
0
3
1 2
6 5
4 4


Output

1
2
0

Note

On the first operation, a new string "0110" is created. For k = 1 the two possible binary strings of length k are "0" and "1", they are substrings of the new string. For k = 2 and greater there exist strings of length k that do not appear in this string (for k = 2 such string is "00"). So the answer is 1.

On the second operation the string "01100" is created. Now all strings of length k = 2 are present.

On the third operation the string "1111111111" is created. There is no zero, so the answer is 0.

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

/*
 public class _868D {

 }

 */

public class _868D {

  int max = 6;

  class ex {
    String prefix;
    String suffix;

    int lastposs = 0;

    HashSet[] set = new HashSet[max + 1];

    public ex(String prefix, String suffix) {
      super();
      this.prefix = prefix;
      this.suffix = suffix;

      for (int i = 1; i <= max; i++)
        this.set[i] = new HashSet<Integer>();
    }

    void add(int num, int size) {
      set[size].add(num);
    }

    void addAll(Set<Integer> nums, int size) {
      set[size].addAll(nums);
    }
  }

  public void solve() throws FileNotFoundException {
    InputStream inputStream = System.in;

    InputHelper inputHelper = new InputHelper(inputStream);

    PrintStream out = System.out;

    // actual solution
    int n = inputHelper.readInteger();

    String[] s = new String[n];

    for (int i = 0; i < n; i++) {
      s[i] = inputHelper.read();
    }

    int[] masks = new int[max + 1];

    for (int i = 1; i <= max; i++) {
      masks[i] = (1 << i) - 1;
    }

    int m = inputHelper.readInteger();

    ex[] exs = new ex[n + m + 1];

    for (int i = 1; i <= n; i++) {

      int maxx = Math.min(max, s[i - 1].length());

      exs[i] = new ex(s[i - 1].substring(0, maxx), s[i - 1].substring(s[i - 1].length() - maxx));
      for (int j = 1; j <= max; j++) {
        if (j > s[i - 1].length()) {
          break;
        }

        String init = s[i - 1].substring(0, j);

        int sum = binToVal(init);

        exs[i].add(sum, j);

        for (int k = j; k < s[i - 1].length(); k++) {
          sum <<= 1;
          if (s[i - 1].charAt(k) == '1') {
            sum += 1;
          }
          sum &= masks[j];

          exs[i].add(sum, j);
        }

        update(masks, exs, i, j);
      }
    }

    for (int q = n + 1; q <= n + m; q++) {
      int a = inputHelper.readInteger();
      int b = inputHelper.readInteger();

      String fp = exs[a].prefix;
      String fs = exs[a].suffix;
      String sp = exs[b].prefix;
      String ss = exs[b].suffix;

      if (fp.length() < max) {
        String fpc = fp;
        fp = fpc + sp.substring(0, Math.min(max - fpc.length(), sp.length()));
      }

      if (ss.length() < max) {
        String ssc = ss;
        ss = fs.substring(Math.max(0, fs.length() - (max - ssc.length()))) + ssc;
      }

      exs[q] = new ex(fp, ss);

      for (int i = 1; i <= max; i++) {
        exs[q].addAll(exs[a].set[i], i);
        exs[q].addAll(exs[b].set[i], i);
      }

      update(masks, exs, q, 1);
      for (int i = 2; i <= max; i++) {

        String suf = fs;
        String pre = sp;

        int sufl = suf.length();
        int prel = pre.length();

        if (sufl + prel < i) {
          break;
        }

        int start = 0;

        String is = null;
        int sum;

        if (sufl < (i - 1)) {
          start = i - 1 - sufl;
          is = suf + pre.substring(0, start);
          sum = binToVal(is);
        } else {
          is = suf.substring(sufl - (i - 1));
          sum = binToVal(is);
        }

        for (int j = start; j < Math.min(i - 1, prel); j++) {
          sum <<= 1;

          if (pre.charAt(j) == '1') {
            sum += 1;
          }

          sum &= masks[i];

          exs[q].set[i].add(sum);
        }

        update(masks, exs, q, i);
      }

      System.out.println(exs[q].lastposs);
    }
    // end here
  }

  Integer binToVal(String binaryStr) {
    int sum = 0;
    for (int k = 0; k < binaryStr.length(); k++) {
      sum <<= 1;
      if (binaryStr.charAt(k) == '1') {
        sum += 1;
      }
    }
    return sum;
  }

  private void update(int[] masks, ex[] exs, int i, int size) {
    if (exs[i].set[size].size() == masks[size] + 1) {
      exs[i].lastposs = Math.max(exs[i].lastposs, size);
    }
  }

  public static void main(String[] args) throws FileNotFoundException {
    (new _868D()).solve();
  }

  class InputHelper {
    StringTokenizer tokenizer = null;
    private BufferedReader bufferedReader;

    public InputHelper(InputStream inputStream) {
      InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
      bufferedReader = new BufferedReader(inputStreamReader, 16384);
    }

    public String read() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String line = bufferedReader.readLine();
          if (line == null) {
            return null;
          }
          tokenizer = new StringTokenizer(line);
        } catch (IOException e) {
          e.printStackTrace();
        }
      }

      return tokenizer.nextToken();
    }

    public Integer readInteger() {
      return Integer.parseInt(read());
    }

    public Long readLong() {
      return Long.parseLong(read());
    }
  }
}