#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#define CMAX 26
#define OFFSET 'a'
struct Node {int nxt[CMAX + 1]; int exist; vector<int> accept;
    Node() : exist(0) { memset(nxt, -1, sizeof(nxt)); }};
struct Trie {
    vector<Node> nodes; int root;Trie() : root(0) { nodes.push_back(Node()); }
    void upd_d(int node, int id) { nodes[node].accept.push_back(id); }
    void upd_c(int node, int child, int id) { ++nodes[node].exist; }
    void add(const string &str, int sindex, int nindex, int id){
        if (sindex == str.size()) upd_d(nindex, id); else {const int c = str[sindex] - OFFSET;
        if(nodes[nindex].nxt[c]==-1){nodes[nindex].nxt[c]=(int)nodes.size();nodes.push_back(Node());}
        add(str, sindex + 1, nodes[nindex].nxt[c], id);upd_c(nindex, nodes[nindex].nxt[c], id);}}
    void add(const string &str, int id) { add(str, 0, 0, id); }
    void add(const string &str) { add(str, nodes[0].exist); }
    int size() { return (nodes[0].exist); }int nodesize() { return ((int)nodes.size()); }};
struct AhoCorasick : Trie {
    static const int FAIL = CMAX; vector<int> correct; AhoCorasick() : Trie() {}
    void build() {correct.resize(nodes.size());
        rep(i, 0, nodes.size()) correct[i] = (int)nodes[i].accept.size();
        queue<int> que; rep(i, 0, CMAX + 1) { if (~nodes[0].nxt[i]) {
        nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;que.emplace(nodes[0].nxt[i]);}else nodes[0].nxt[i] = 0;}
        while(!que.empty()){Node &now=nodes[que.front()];correct[que.front()]+=correct[now.nxt[FAIL]];
        que.pop();for (int i = 0; i < CMAX; i++) {if (now.nxt[i] == -1) continue;
        int fail = now.nxt[FAIL];while (nodes[fail].nxt[i] == -1) fail = nodes[fail].nxt[FAIL];
        nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];auto &u = nodes[now.nxt[i]].accept;
        auto &v = nodes[nodes[fail].nxt[i]].accept;vector<int> accept;
        set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));u = accept;
        que.emplace(now.nxt[i]);}}}
    int match(const string &str, vector< int > &result, int now = 0) {
        result.assign(size(), 0);int count = 0;for (auto &c : str) {
        while (nodes[now].nxt[c - OFFSET] == -1) now = nodes[now].nxt[FAIL];
        now = nodes[now].nxt[c - OFFSET];count += correct[now];
        for (auto &v : nodes[now].accept) ++result[v];}return count;}
    int next(int now, char c) {while (nodes[now].nxt[c - OFFSET] == -1) now = nodes[now].nxt[FAIL];
        return nodes[now].nxt[c - OFFSET];}
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/








string S;
int N;
string P[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> N;
    rep(i, 0, N) cin >> P[i];

    AhoCorasick ac;
    rep(i, 0, N) ac.add(P[i]);
    ac.build();

    int ans = 0;
    int cur = ac.root;

    fore(c, S) {
        cur = ac.next(cur, c);
        if (0 < ac.nodes[cur].accept.size()) {
            ans++;
            cur = ac.root;
        }
    }

    cout << ans << endl;
}

### Prompt

Please formulate a cpp solution to the following problem:

G： 検閲により置換 (Censored String)

Problem Statement

You are given the string S, and the set of strings \mathcal P whose size is N. Now we consider applying the following operation to S:

* Choose exactly one character in S, and replace it with '*'.



Let s_i be a i-th character of S, S_{ij} be a consecutive substring in S such that  S = s_i s_{i+1} $\cdots$  s_j, and p_k as the k-th string of P. Your task is to calculate the minimum number of operations for satisfying the following condition.

* For all pairs (S_{ij}, p_k), it is satisfied that S_{ij} \neq p_k.



Input

An input is given in the following format.


S
N
p_1
p_2
$\vdots$
p_N


* In line 1, you are given the string S.
* In line 2, given an integer N. N means the size of P.
* From line 3 to the end, given p_i, the i-th string of P.



Constraints

* 1 \leq |S| \leq 10^5
* 1 \leq N \leq 10^5
* 1 \leq |p_1| + |p_2| +  $\cdots$  + |p_N| \leq 10^5
* If i \neq j, it is guaranteed that p_i \neq p_j
* S, and p_i include lowercase letters only



Output

Print the minimum number of operations in one line.

Sample Input 1


brainfuck
1
fuck


Sample Output 1


1

For example, if you change "brainfuck" into "brainf*ck", you can satisfy the condition. You have to perform operation at least once, and it is the minimum value.

Sample Input 2


aaa
1
a


Sample Output 2


3

You have to operate for all characters.

Sample Input 3


hellshakeyano
3
hell
shake
key


Sample Output 3


2

In this case, for example, if you change "hellshakeyano" into "h*llsha*eyano", you can satisfy the condition. Notice if you replace one character, it might happen that several strings in the set P, which appear as the consecutive substring of S, simultaneously disappear.





Example

Input

brainfuck
1
fuck


Output

1

### Response

```cpp
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#define CMAX 26
#define OFFSET 'a'
struct Node {int nxt[CMAX + 1]; int exist; vector<int> accept;
    Node() : exist(0) { memset(nxt, -1, sizeof(nxt)); }};
struct Trie {
    vector<Node> nodes; int root;Trie() : root(0) { nodes.push_back(Node()); }
    void upd_d(int node, int id) { nodes[node].accept.push_back(id); }
    void upd_c(int node, int child, int id) { ++nodes[node].exist; }
    void add(const string &str, int sindex, int nindex, int id){
        if (sindex == str.size()) upd_d(nindex, id); else {const int c = str[sindex] - OFFSET;
        if(nodes[nindex].nxt[c]==-1){nodes[nindex].nxt[c]=(int)nodes.size();nodes.push_back(Node());}
        add(str, sindex + 1, nodes[nindex].nxt[c], id);upd_c(nindex, nodes[nindex].nxt[c], id);}}
    void add(const string &str, int id) { add(str, 0, 0, id); }
    void add(const string &str) { add(str, nodes[0].exist); }
    int size() { return (nodes[0].exist); }int nodesize() { return ((int)nodes.size()); }};
struct AhoCorasick : Trie {
    static const int FAIL = CMAX; vector<int> correct; AhoCorasick() : Trie() {}
    void build() {correct.resize(nodes.size());
        rep(i, 0, nodes.size()) correct[i] = (int)nodes[i].accept.size();
        queue<int> que; rep(i, 0, CMAX + 1) { if (~nodes[0].nxt[i]) {
        nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;que.emplace(nodes[0].nxt[i]);}else nodes[0].nxt[i] = 0;}
        while(!que.empty()){Node &now=nodes[que.front()];correct[que.front()]+=correct[now.nxt[FAIL]];
        que.pop();for (int i = 0; i < CMAX; i++) {if (now.nxt[i] == -1) continue;
        int fail = now.nxt[FAIL];while (nodes[fail].nxt[i] == -1) fail = nodes[fail].nxt[FAIL];
        nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];auto &u = nodes[now.nxt[i]].accept;
        auto &v = nodes[nodes[fail].nxt[i]].accept;vector<int> accept;
        set_union(begin(u), end(u), begin(v), end(v), back_inserter(accept));u = accept;
        que.emplace(now.nxt[i]);}}}
    int match(const string &str, vector< int > &result, int now = 0) {
        result.assign(size(), 0);int count = 0;for (auto &c : str) {
        while (nodes[now].nxt[c - OFFSET] == -1) now = nodes[now].nxt[FAIL];
        now = nodes[now].nxt[c - OFFSET];count += correct[now];
        for (auto &v : nodes[now].accept) ++result[v];}return count;}
    int next(int now, char c) {while (nodes[now].nxt[c - OFFSET] == -1) now = nodes[now].nxt[FAIL];
        return nodes[now].nxt[c - OFFSET];}
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/








string S;
int N;
string P[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> N;
    rep(i, 0, N) cin >> P[i];

    AhoCorasick ac;
    rep(i, 0, N) ac.add(P[i]);
    ac.build();

    int ans = 0;
    int cur = ac.root;

    fore(c, S) {
        cur = ac.next(cur, c);
        if (0 < ac.nodes[cur].accept.size()) {
            ans++;
            cur = ac.root;
        }
    }

    cout << ans << endl;
}

```