Problem: During the study of the Martians Petya clearly understood that the Martians are absolutely lazy. They like to sleep and don't like to wake up. 

Imagine a Martian who has exactly n eyes located in a row and numbered from the left to the right from 1 to n. When a Martian sleeps, he puts a patch on each eye (so that the Martian morning doesn't wake him up). The inner side of each patch has an uppercase Latin letter. So, when a Martian wakes up and opens all his eyes he sees a string s consisting of uppercase Latin letters. The string's length is n. 

"Ding dong!" — the alarm goes off. A Martian has already woken up but he hasn't opened any of his eyes. He feels that today is going to be a hard day, so he wants to open his eyes and see something good. The Martian considers only m Martian words beautiful. Besides, it is hard for him to open all eyes at once so early in the morning. So he opens two non-overlapping segments of consecutive eyes. More formally, the Martian chooses four numbers a, b, c, d, (1 ≤ a ≤ b < c ≤ d ≤ n) and opens all eyes with numbers i such that a ≤ i ≤ b or c ≤ i ≤ d. After the Martian opens the eyes he needs, he reads all the visible characters from the left to the right and thus, he sees some word.

Let's consider all different words the Martian can see in the morning. Your task is to find out how many beautiful words are among them.

Input

The first line contains a non-empty string s consisting of uppercase Latin letters. The strings' length is n (2 ≤ n ≤ 105). The second line contains an integer m (1 ≤ m ≤ 100) — the number of beautiful words. Next m lines contain the beautiful words pi, consisting of uppercase Latin letters. Their length is from 1 to 1000. All beautiful strings are pairwise different.

Output

Print the single integer — the number of different beautiful strings the Martian can see this morning.

Examples

Input

ABCBABA
2
BAAB
ABBA


Output

1

Note

Let's consider the sample test. There the Martian can get only the second beautiful string if he opens segments of eyes a = 1, b = 2 and c = 4, d = 5 or of he opens segments of eyes a = 1, b = 2 and c = 6, d = 7. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpdd = vector<pdd>;
template <typename T>
void ckmin(T& a, const T& b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T& a, const T& b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2>& p);
template <class T>
void re(vector<T>& a);
template <class T, size_t SZ>
void re(array<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg& first, Args&... rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& a) {
  for (int i = 0; i < (int((a).size())); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ>& a) {
  for (int i = 0; i < (SZ); i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <class T1, class T2>
void pr(const pair<T1, T2>& x);
template <class T, size_t SZ>
void pr(const array<T, SZ>& x);
template <class T>
void pr(const vector<T>& x);
template <class T>
void pr(const set<T>& x);
template <class T1, class T2>
void pr(const map<T1, T2>& x);
template <class T>
void pr(const T& x) {
  cout << x;
}
template <class Arg, class... Args>
void pr(const Arg& first, const Args&... rest) {
  pr(first);
  pr(rest...);
}
template <class T1, class T2>
void pr(const pair<T1, T2>& x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, bool pretty = true>
void prContain(const T& x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto& a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T& x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T, size_t SZ>
void pr(const array<T, SZ>& x) {
  prContain(x);
}
template <class T>
void pr(const vector<T>& x) {
  prContain(x);
}
template <class T>
void pr(const set<T>& x) {
  prContain(x);
}
template <class T1, class T2>
void pr(const map<T1, T2>& x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg& first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg& first, const Args&... rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::const_iterator find(const vector<T>& v, const T& x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(const vector<T>& v, const T& x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename T1, typename T2>
typename vector<pair<T1, T2>>::iterator lower_bound(
    const vector<pair<T1, T2>>& v, const T1& x) {
  return lower_bound(
      (v).begin(), (v).end(), x,
      [](pair<T1, T2> a, pair<T1, T2> b) { return a.first < b.first; });
}
template <typename T1, typename T2>
typename vector<pair<T1, T2>>::iterator upper_bound(
    const vector<pair<T1, T2>>& v, const T1& x) {
  return upper_bound(
      (v).begin(), (v).end(), x,
      [](pair<T1, T2> a, pair<T1, T2> b) { return a.first < b.first; });
}
}  // namespace __algorithm
using namespace __algorithm;
struct __monostate {
  friend istream& operator>>(istream& is,
                             const __attribute__((unused)) __monostate& ms) {
    return is;
  }
  friend ostream& operator<<(ostream& os,
                             const __attribute__((unused)) __monostate& ms) {
    return os;
  }
} ms;
namespace __io {
FILE* setIn(string second) { return freopen(second.c_str(), "r", stdin); }
FILE* setOut(string second) { return freopen(second.c_str(), "w", stdout); }
void setIO(string second = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << setprecision(15);
  if (int((second).size())) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
}  // namespace __io
using namespace __io;
template <typename T, typename F>
struct sparse_table {
  int SZ;
  F tt;
  vector<vector<T>> table;
  sparse_table() {}
  template <typename I>
  sparse_table(int SZ_, F tt_, I init) : SZ(SZ_), tt(tt_) {
    const int L = 32 - __builtin_clz(max(SZ - 1, 1));
    table.resize(L, vector<T>(SZ));
    for (int i = 0; i < SZ; i++) table[0][i] = init(i);
    for (int l = 0; l + 1 < L; l++)
      for (int i = 0; i + (2 << l) <= SZ; i++)
        table[l + 1][i] = tt(table[l][i], table[l][i + (1 << l)]);
  }
  T operator()(int i, int j) const {
    assert(0 <= i && i < j && j <= SZ);
    int l = j - i - 1 ? 31 - __builtin_clz(j - i - 1) : 0;
    return tt(table[l][i], table[l][j - (1 << l)]);
  }
};
enum BACKFILL { CYCLIC, NEG_INF, POS_INF };
template <BACKFILL FILL>
struct suffix_array {
  int SZ;
  vector<vector<int>> rank_of;
  vector<int> by_rank;
  vector<int> lcp;
  static struct smaller {
    int operator()(int x, int y) const { return min(x, y); }
  } lcp_cmp;
  sparse_table<int, smaller> lcp_rmq;
  template <typename I>
  suffix_array(I begin, I end) {
    vi input;
    for (I iter = begin; iter != end; iter = next(iter)) input.push_back(*iter);
    SZ = int(input.size());
    vi uniq = input;
    sort(uniq.begin(), uniq.end());
    uniq.erase(unique(uniq.begin(), uniq.end()), uniq.end());
    for (int& val : input)
      val = (lower_bound(uniq.begin(), uniq.end(), val) - uniq.begin());
    rank_of.push_back(input);
    vi ct(SZ);
    for (int i = 0; i < SZ; i++) ct[input[i]]++;
    for (int i = 0; i < SZ - 1; i++) ct[i + 1] += ct[i];
    by_rank.resize(SZ);
    for (int i = SZ - 1; i >= 0; i--) by_rank[--ct[input[i]]] = i;
    vector<int> by_rank_updated(SZ);
    for (int len = 1; len < SZ; len *= 2) {
      int tail = 0;
      if (FILL == NEG_INF)
        for (int i = SZ - len; i < SZ; i++) by_rank_updated[tail++] = i;
      for (int rank = 0; rank < SZ; rank++)
        if (by_rank[rank] >= len)
          by_rank_updated[tail++] = by_rank[rank] - len;
        else if (FILL == CYCLIC)
          by_rank_updated[tail++] = by_rank[rank] - len + SZ;
      if (FILL == POS_INF)
        for (int i = SZ - len; i < SZ; i++) by_rank_updated[tail++] = i;
      swap(by_rank, by_rank_updated);
      fill(ct.begin(), ct.end(), 0);
      for (int i = 0; i < SZ; i++) ct[rank_of.back()[i]]++;
      for (int i = 0; i < SZ - 1; i++) ct[i + 1] += ct[i];
      for (int i = SZ - 1; i >= 0; i--)
        by_rank_updated[--ct[rank_of.back()[by_rank[i]]]] = by_rank[i];
      swap(by_rank, by_rank_updated);
      vi new_ranks(SZ);
      pair<int, int> prev = {rank(by_rank[0]), rank(by_rank[0] + len)};
      for (int i = 1; i < SZ; i++) {
        pair<int, int> cur = {rank(by_rank[i]), rank(by_rank[i] + len)};
        new_ranks[by_rank[i]] = new_ranks[by_rank[i - 1]] + (prev != cur);
        prev = cur;
      }
      rank_of.push_back(new_ranks);
    }
    lcp.resize(SZ - 1);
    int len = 0;
    for (int i = 0; i < SZ; i++) {
      if (rank(i) == SZ - 1) {
        len = 0;
        continue;
      }
      int j = by_rank[rank(i) + 1];
      while (i + len < SZ && j + len < SZ && input[i + len] == input[j + len])
        len++;
      lcp[rank(i)] = len;
      if (len) --len;
    }
    lcp_rmq = sparse_table<int, smaller>(lcp.size(), lcp_cmp,
                                         [&](int i) { return lcp[i]; });
  }
  int rank(int i) const {
    if (i < SZ) {
      return rank_of.back()[i];
    } else
      switch (FILL) {
        case CYCLIC:
          return rank_of.back()[i - SZ];
        case NEG_INF:
          return -1;
        case POS_INF:
          return SZ;
      }
  }
  int suffix_at_rank(int r) const { return by_rank[r]; }
  int longest_common_prefix(int i, int j) const {
    assert(0 <= i && i < SZ && 0 <= j && j < SZ);
    if (i == j) return SZ - i;
    i = rank(i);
    j = rank(j);
    if (i > j) swap(i, j);
    return lcp_rmq(i, j);
  }
  pair<int, int> ranks_with_prefix(int pos, int len) {
    assert(0 <= pos && pos + len <= SZ);
    auto less_than = [&](int other_pos, int arg) {
      return longest_common_prefix(pos, other_pos) < arg;
    };
    auto geq = [&](int other_pos, int arg) {
      return longest_common_prefix(pos, other_pos) >= arg;
    };
    return make_pair(
        lower_bound(by_rank.begin(), by_rank.begin() + rank(pos), len,
                    less_than) -
            by_rank.begin(),
        lower_bound(by_rank.begin() + rank(pos), by_rank.end(), len, geq) -
            by_rank.begin());
  }
};
template <typename T, typename F>
struct segment_tree {
  int SZ;
  T id;
  F tt;
  vector<T> table;
  segment_tree() {}
  segment_tree(int SZ_, T id_, F tt_) : SZ(SZ_), id(id_), tt(tt_) {
    table.resize(2 * SZ, id);
  }
  template <typename L>
  void set_leaves(L create) {
    for (int i = 0; i < SZ; i++) table[SZ + i] = create(i);
    for (int i = SZ - 1; i; i--) table[i] = tt(table[2 * i], table[2 * i + 1]);
  }
  void replace(int i, T v) {
    table[i += SZ] = v;
    for (i /= 2; i > 0; i /= 2) {
      table[i] = tt(table[2 * i], table[2 * i + 1]);
    }
  }
  T operator()(int i, int j) const {
    T left = id, right = id;
    for (i += SZ, j += SZ; i < j; i /= 2, j /= 2) {
      if (i & 1) left = tt(left, table[i++]);
      if (j & 1) right = tt(table[--j], right);
    }
    return tt(left, right);
  }
  const T& operator[](int i) const { return table[SZ + i]; }
};
int main() {
  setIO();
  string S;
  re(S);
  int N;
  re(N);
  vector<string> words(N);
  re(words);
  vector<int> concat;
  for (auto& c : S) concat.push_back(c - 'A');
  vi begin(N);
  for (int i = 0; i < (N); i++) {
    concat.push_back(26 + i);
    begin[i] = int((concat).size());
    for (auto& c : words[i]) {
      concat.push_back(c - 'A');
    }
  }
  suffix_array<NEG_INF> sa((concat).begin(), (concat).end());
  vi by_rank = sa.by_rank;
  struct node {
    int lo, hi;
  };
  auto nn = [](node a, node b) {
    return node{min(a.lo, b.lo), max(a.hi, b.hi)};
  };
  segment_tree<node, decltype(nn)> st(int((by_rank).size()),
                                      node{INT_MAX / 2, INT_MIN / 2}, nn);
  for (int rank = 0; rank < (int((concat).size())); rank++) {
    int inx = sa.by_rank[rank];
    if (inx < int((S).size())) {
      st.replace(rank, {inx, inx});
    }
  }
  int ans = 0;
  for (int i = 0; i < (N); i++) {
    for (int left = 1; left < int((words[i]).size()); left++) {
      int right = int((words[i]).size()) - left;
      pair<int, int> occur_left = sa.ranks_with_prefix(begin[i], left);
      int inx_left = st(occur_left.first, occur_left.second).lo;
      pair<int, int> occur_right = sa.ranks_with_prefix(begin[i] + left, right);
      int inx_right = st(occur_right.first, occur_right.second).hi;
      if (inx_left + left <= inx_right) {
        ans++;
        break;
      }
    }
  }
  ps(ans);
  return 0;
}