Borya has recently found a big electronic display. The computer that manages the display stores some integer number. The number has n decimal digits, the display shows the encoded version of the number, where each digit is shown using some lowercase letter of the English alphabet.

There is a legend near the display, that describes how the number is encoded. For each digit position i and each digit j the character c is known, that encodes this digit at this position. Different digits can have the same code characters.

Each second the number is increased by 1. And one second after a moment when the number reaches the value that is represented as n 9-s in decimal notation, the loud beep sounds. 

Andrew knows the number that is stored in the computer. Now he wants to know how many seconds must pass until Borya can definitely tell what was the original number encoded by the display. Assume that Borya can precisely measure time, and that the encoded number will first be increased exactly one second after Borya started watching at the display.

Input

Input data contains multiple test cases. The first line of input contains t (1 ≤ t ≤ 100) — the number of test cases. 

Each test case is described as follows. The first line of the description contains n (1 ≤ n ≤ 18) — the number of digits in the number. The second line contains n decimal digits without spaces (but possibly with leading zeroes) — the number initially stored in the display computer. The following n lines contain 10 characters each. The j-th character of the i-th of these lines is the code character for a digit j - 1 in position i, most significant digit positions are described first.

Output

For each test case print an integer: the number of seconds until Borya definitely knows what was the initial number stored on the display of the computer. Do not print leading zeroes.

Example

Input

3
2
42
abcdefghij
jihgfedcba
2
42
aaaaaaaaaa
aaaaaaaaaa
1
2
abcdabcdff


Output

0
58
2
#include <bits/stdc++.h>
using namespace std;
bool __hack = std::ios::sync_with_stdio(false);
auto __hack1 = cin.tie(nullptr);
namespace option_detail {
struct NoneHelper {};
}  // namespace option_detail
template <class Value>
class Option {
 public:
  static_assert(!std::is_reference<Value>::value,
                "Option may not be used with reference types");
  static_assert(!std::is_abstract<Value>::value,
                "Option may not be used with abstract types");
  Value* get_pointer() && = delete;

 private:
  struct StorageTriviallyDestructible {
    bool hasValue;
  };
  struct StorageNonTriviallyDestructible {
    union {
      Value value;
    };
    bool hasValue;
    ~StorageNonTriviallyDestructible() { clear(); }
    void clear() {
      if (hasValue) {
        hasValue = false;
        value.~Value();
      }
    }
  };
  using Storage =
      typename std::conditional<std::is_trivially_destructible<Value>::value,
                                StorageTriviallyDestructible,
                                StorageNonTriviallyDestructible>::type;
  Storage storage_;
};
template <class V>
bool operator<(const Option<V>&, const V& other) = delete;
template <class V>
bool operator<=(const Option<V>&, const V& other) = delete;
template <class V>
bool operator>=(const Option<V>&, const V& other) = delete;
template <class V>
bool operator>(const Option<V>&, const V& other) = delete;
template <class V>
bool operator<(const V& other, const Option<V>&) = delete;
template <class V>
bool operator<=(const V& other, const Option<V>&) = delete;
template <class V>
bool operator>=(const V& other, const Option<V>&) = delete;
template <class V>
bool operator>(const V& other, const Option<V>&) = delete;
namespace template_util {
constexpr int bytecount(uint64_t x) { return x ? 1 + bytecount(x >> 8) : 0; }
template <int N>
struct bytetype {};
template <>
struct bytetype<4> {};
template <>
struct bytetype<3> {};
template <>
struct bytetype<2> {};
template <>
struct bytetype<1> {};
template <>
struct bytetype<0> {};
template <uint64_t N>
struct minimal_uint : bytetype<bytecount(N)> {};
}  // namespace template_util
namespace index_iterator_impl {
template <class T>
struct member_dispatch_helper {
 private:
  T value;
};
template <class C, bool reverse = false>
struct index_iterator {
  typedef decltype(((C*)nullptr)->operator[](size_t(0))) reference;
  typedef conditional<
      is_reference<reference>::value,
      typename add_pointer<typename remove_reference<reference>::type>::type,
      member_dispatch_helper<typename remove_reference<reference>::type>>
      pointer;
  static const ptrdiff_t dir = reverse ? -1 : 1;
  index_iterator() = default;
  inline bool operator!=(const index_iterator<C, reverse>& o) {
    return index != o.index;
  }
  inline bool operator<(const index_iterator<C, reverse>& o) {
    return reverse ? index > o.index : index < o.index;
  }
  inline bool operator>(const index_iterator<C, reverse>& o) {
    return reverse ? index < o.index : index > o.index;
  }
  inline bool operator<=(const index_iterator<C, reverse>& o) {
    return reverse ? index >= o.index : index <= o.index;
  }
  inline bool operator>=(const index_iterator<C, reverse>& o) {
    return reverse ? index <= o.index : index >= o.index;
  }
  inline reference operator*() { return (*container)[index]; }
  inline const reference operator*() const { return (*container)[index]; }
  inline pointer operator->() { return pointer((*container)[index]); }
  inline index_iterator<C, reverse>& operator++() {
    index += dir;
    return *this;
  }
  inline index_iterator<C, reverse> operator++(int) {
    auto copy = *this;
    index += dir;
    return copy;
  }
  inline index_iterator<C, reverse>& operator--() {
    index -= dir;
    return *this;
  }
  inline index_iterator<C, reverse> operator--(int) {
    auto copy = *this;
    index -= dir;
    return copy;
  }
  inline index_iterator<C, reverse>& operator+=(ptrdiff_t n) {
    index += dir * n;
    return *this;
  };
  inline index_iterator<C, reverse>& operator-=(ptrdiff_t n) {
    index -= dir * n;
    return *this;
  };
  inline friend index_iterator<C, reverse> operator-(
      index_iterator<C, reverse> a, ptrdiff_t n) {
    return a -= n;
  };
  inline friend index_iterator<C, reverse> operator+(
      ptrdiff_t n, index_iterator<C, reverse> a) {
    return a += n;
  };
  inline friend index_iterator<C, reverse> operator+(
      index_iterator<C, reverse> a, ptrdiff_t n) {
    return a += n;
  };
  inline friend ptrdiff_t operator-(const index_iterator<C, reverse>& a,
                                    const index_iterator<C, reverse>& b) {
    return dir * (a.index - b.index);
  };
  inline reference operator[](ptrdiff_t n) {
    return (*container)[index + dir * n];
  };
  inline const reference operator[](ptrdiff_t n) const {
    return (*container)[index + dir * n];
  };

 private:
  C* container;
  ptrdiff_t index;
};
}  // namespace index_iterator_impl
namespace multivec_impl {
template <size_t NDIMS>
struct shape {
  size_t dim, stride;
  shape<NDIMS - 1> subshape;
  shape(size_t dim_, shape<NDIMS - 1>&& s)
      : dim(dim_), stride(s.size()), subshape(std::move(s)) {}
  size_t size() const { return dim * stride; }
};
template <>
struct shape<0> {
  size_t size() const { return 1; }
};
template <size_t I, size_t NDIMS>
struct __shape_traverse {};
template <size_t NDIMS>
struct __shape_traverse<0, NDIMS> {
  static size_t get_dim(const shape<NDIMS>& s) { return s.dim; }
};
template <size_t I, size_t NDIMS>
size_t get_dim(const shape<NDIMS>& s) {
  return __shape_traverse<I, NDIMS>::get_dim(s);
}
template <class Index, class... Rest, size_t NDIMS,
          typename enable_if<is_integral<Index>::value>::type* = nullptr>
size_t get_shift(const shape<NDIMS>& s, size_t cur_shift, Index i, Rest... is) {
  assert(0 <= i && i < s.dim);
  return get_shift(s.subshape, cur_shift + i * s.stride, is...);
}
template <size_t NDIMS>
size_t get_shift(const shape<NDIMS>&, size_t cur_shift) {
  return cur_shift;
}
template <class... T>
shape<sizeof...(T)> make_shape(T... dims);
template <class Dim, class... Rest,
          typename enable_if<is_integral<Dim>::value>::type* = nullptr>
shape<sizeof...(Rest) + 1> make_shape(Dim dim, Rest... dims) {
  assert(dim >= 0);
  return {(size_t)dim, make_shape<Rest...>(dims...)};
}
template <>
shape<0> make_shape() {
  return {};
}
template <template <class T, size_t NDIMS> class Base, class T, size_t NDIMS>
struct vec_mixin : public Base<T, NDIMS> {
  using Base<T, NDIMS>::Base;
  template <size_t I = 0>
  inline size_t dim() const {
    return get_dim<I>(Base<T, NDIMS>::s);
  }
  template <class... Indices, bool enabled = NDIMS == sizeof...(Indices),
            typename enable_if<enabled>::type* = nullptr>
  inline T& operator()(Indices... is) {
    size_t i = multivec_impl::get_shift(Base<T, NDIMS>::s, 0, is...);
    return Base<T, NDIMS>::data[i];
  }
  template <class F, class... Indices, class T1 = vec_mixin,
            typename result_of<F()>::type* = nullptr>
  inline typename enable_if<NDIMS == 1, T1&>::type fill(F f, Indices...) & {
    for (size_t i = 0; i < (dim()); ++i) Base<T, NDIMS>::data[i] = f();
    return *this;
  };
};
template <class T, size_t NDIMS>
struct vec_base {
  inline vec_base(multivec_impl::shape<NDIMS>&& s_)
      : s(move(s_)), data(new T[s.size()]) {}
  inline vec_base(const vec_base& o) : s(o.s), data(new T[s.size()]) {
    memcpy(data.get(), o.data.get(), sizeof(T) * s.size());
  }

 protected:
  multivec_impl::shape<NDIMS> s;
  unique_ptr<T[]> data;
};
}  // namespace multivec_impl
template <class T, size_t NDIMS>
using vec = multivec_impl::vec_mixin<multivec_impl::vec_base, T, NDIMS>;
template <class T, class... NDIMS>
inline vec<T, sizeof...(NDIMS)> make_vec(NDIMS... dims) {
  return {multivec_impl::make_shape(dims...)};
}
template <class T>
T next(istream& in) {
  T ret;
  in >> ret;
  return ret;
}
template <class T, class... Dims>
vec<T, sizeof...(Dims)> next_vec(istream& in, Dims... dims) {
  auto tmp = make_vec<T>(dims...);
  tmp.fill([&]() { return next<T>(in); });
  return tmp;
}
using H = tuple<uint64_t, uint64_t>;
inline H operator*(H a, H b) {
  return H{get<0>(a) * get<1>(b) + get<0>(b), get<1>(a) * get<1>(b)};
}
H zero = H{0, 1};
auto one = [](char c) { return H{c, 239}; };
inline H pow(H x, int64_t pow) {
  assert(pow >= 0);
  H ret = zero;
  while (pow > 0) {
    if (pow & 1) {
      ret = ret * x;
    }
    pow /= 2;
    x = x * x;
  }
  return ret;
}
void solve(istream& in, ostream& out) {
  int n = next<int>(in);
  string vs = next<string>(in);
  auto cs = next_vec<string>(in, n);
  int64_t v = 0;
  int64_t last = 1;
  for (int i = 0; i < (n); ++i) {
    last = 10 * last;
    v = 10 * v + vs[i] - '0';
  }
  auto pow10 = make_vec<int64_t>(n + 1);
  pow10(0) = 1;
  for (int i = 0; i < (n); ++i) {
    pow10(i + 1) = pow10(i) * 10;
  }
  auto chs = make_vec<H>(n, 10);
  for (int i = 0; i < (n); ++i) {
    for (int j = 0; j < (10); ++j) {
      chs(i, j) = pow(one(cs(i)[j]), pow10(n - i - 1));
    }
  }
  auto chs10 = make_vec<H>(n);
  for (int i = 0; i < (n); ++i) {
    chs10(i) = zero;
    for (int j = 0; j < (10); ++j) {
      chs10(i) = chs10(i) * chs(i, j);
    }
  }
  auto h = [&](int64_t from, int64_t to, int at) {
    H cur;
    int64_t p10 = pow10(n - at - 1);
    if (from / p10 == to / p10) {
      cur = pow(one(cs(at)[from / p10 % 10]), to - from);
    } else {
      cur = pow(one(cs(at)[from / p10 % 10]), (from / p10 + 1) * p10 - from);
      int64_t from1 = from / p10 + 1, to1 = to / p10;
      while (from1 < to1 && from1 % 10 != 0) {
        cur = cur * chs(at, from1 % 10);
        from1++;
      }
      int64_t add10 = (to1 - from1) / 10;
      cur = cur * pow(chs10(at), add10);
      from1 += add10 * 10;
      while (from1 < to1) {
        cur = cur * chs(at, from1 % 10);
        from1++;
      }
      cur = cur * pow(one(cs(at)[to / p10 % 10]), to - (to / p10) * p10);
    }
    return cur;
  };
  int64_t l = -1, r = last - v;
  while (l + 1 < r) {
    int64_t mid = (l + r) / 2;
    auto h0 = make_vec<H>(n);
    for (int at = 0; at < (n); ++at) {
      h0(at) = h(v, v + mid + 1, at);
    }
    for (int at = 0; at < (n); ++at) {
      int d = vs[at] - '0';
      for (int d1 = 0; d1 < (10); ++d1) {
        if (d == d1 || cs(at)[d] != cs(at)[d1]) {
          continue;
        }
        int64_t v1 = v + pow10(n - at - 1) * (d1 - d);
        if (v1 + mid + 1 > last) {
          continue;
        }
        for (int at1 = 0; at1 < (at + 1); ++at1) {
          if (h0(at1) != h(v1, v1 + mid + 1, at1)) {
            goto cnt;
          }
        }
        l = mid;
        goto next;
      cnt:;
      }
    }
    r = mid;
  next:;
  }
  out << r << endl;
}
int main() {
  int tests;
  cin >> tests;
  for (int test = 0; test < tests; ++test) {
    solve(cin, cout);
  }
  return 0;
}
