Problem: This problem is about imaginary languages BHTML and BCSS, which slightly resemble HTML and CSS. Read the problem statement carefully as the resemblance is rather slight and the problem uses very simplified analogs.

You are given a BHTML document that resembles HTML but is much simpler. It is recorded as a sequence of opening and closing tags. A tag that looks like "<tagname>" is called an opening tag and a tag that looks like "</tagname>" is called a closing tag. Besides, there are self-closing tags that are written as "<tagname/>" and in this problem they are fully equivalent to "<tagname></tagname>". All tagnames in this problem are strings consisting of lowercase Latin letters with length from 1 to 10 characters. Tagnames of different tags may coincide.

The document tags form a correct bracket sequence, that is, we can obtain an empty sequence from the given one using the following operations: 

  * remove any self-closing tag "<tagname/>", 
  * remove a pair of an opening and a closing tag that go consecutively (in this order) and have the same names. In other words, remove substring "<tagname></tagname>". 



For example, you may be given such document: "<header><p><a/><b></b></p></header><footer></footer>" but you may not be given documents "<a>", "<a></b>", "</a><a>" or "<a><b></a></b>".

Obviously, for any opening tag there is the only matching closing one — each such pair is called an element. A self-closing tag also is an element. Let's consider that one element is nested inside another one, if tags of the first element are between tags of the second one. An element is not nested to itself. For instance, in the example above element "b" is nested in "header" and in "p", but it isn't nested in "a" and "footer", also it isn't nested to itself ("b"). Element "header" has three elements nested in it, and "footer" has zero.

We need the BCSS rules to apply styles when displaying elements of the BHTML documents. Each rule is recorded as a subsequence of words "x1 x2 ... xn". This rule has effect over all such elements t, which satisfy both conditions from the list:

  * there is a sequence of nested elements with tagnames "x1", "x2", ..., "xn" (that is, the second element is nested in the first one, the third element is nested in the second one and so on), 
  * this sequence ends with element t (i.e. tagname of element t equals "xn"). 



For example, element "b" meets the conditions of the rule "a b" if for element "b" exists element "a" in which it is nested. Element "c" meets the conditions of the rule "a b b c", if three elements exist: "a", "b", "b", and in the chain "a"-"b"-"b"-"c" each following element is nested in the previous one.

Given a BHTML document and a set of BCSS rules, write a program that determines the number of elements that meet the conditions of each rule.

Input

The first line of the input contains a BHTML-document. The document has length from 4 to 106 characters. The document has a correct structure, doesn't contain spaces or any other unnecessary characters. Tagnames consist of lowercase Latin letters, their lengths are from 1 to 10 characters.

The second line contains an integer m (1 ≤ m ≤ 200) — the number of queries. Then m lines contain the queries, one per line. Each query is a sequence x1, x2, ..., xn, where xi is the i-th element of the query, and n (1 ≤ n ≤ 200) is the number of elements in the query. The elements are separated by single spaces. Each query doesn't begin with and doesn't end with a space. Each query element is a sequence of lowercase Latin letters with length from 1 to 10.

Output

Print m lines, the j-th line should contain the number of elements of the document that correspond to the j-th BCSS-rule. If there are no such elements at all, print on the line 0.

Examples

Input

&lt;a&gt;&lt;b&gt;&lt;b&gt;&lt;/b&gt;&lt;/b&gt;&lt;/a&gt;&lt;a&gt;&lt;b&gt;&lt;/b&gt;&lt;b&gt;&lt;v/&gt;&lt;/b&gt;&lt;/a&gt;&lt;b&gt;&lt;/b&gt;
4
a
a b b
a b
b a


Output

2
1
4
0


Input

&lt;b&gt;&lt;aa/&gt;&lt;/b&gt;&lt;aa&gt;&lt;b/&gt;&lt;b/&gt;&lt;/aa&gt;
5
aa b
b
aa
b aa
a


Output

2
3
2
1
0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma comment(linker, / STACK : 2000010)
using namespace std;
struct Node {
  string data;
  Node* firstChild;
  Node* nextSibling;
  long id;
  long tagId;
  Node(string aData, Node* aChild = NULL, Node* aSibling = NULL, long aId = 0) {
    data = aData;
    firstChild = aChild;
    nextSibling = aSibling;
    tagId = aId;
  }
};
long PreOrder(Node* apRoot, int aPos);
Node* BuildNaryTree(string htmlDoc);
void PushToStack(Node* node);
void PopFromStack(Node** node);
class HashTable {
 public:
  HashTable(long aSize);
  ~HashTable();
  void put(string aTag);
  bool contains(string aTag);
  long get(string aTag);
  void remove(string aTag);
  long size();

 private:
  std::unordered_map<string, long> mLookupTable;
};
const int MaxQueryCount = 5000;
const long MaxNodeCount = 350000;
string* gQuery = NULL;
long* lQuery = NULL;
int gQTagCount = 0;
HashTable* g_pHashTable = NULL;
long gStack[MaxNodeCount] = {0};
long gStackTop = -1;
Node* gNode[MaxNodeCount] = {0};
long gNodeCount = 0;
void PushToStack(Node* node) {
  gStackTop++;
  if (gStackTop > MaxNodeCount) {
    printf("\n Stack Overflow machi...");
    return;
  }
  gStack[gStackTop] = (long)node;
}
void PopFromStack(Node** node) {
  if (gStackTop == -1) {
    *node = NULL;
    return;
  }
  *node = (Node*)gStack[gStackTop];
  gStackTop -= 1;
}
Node* BuildNaryTree(string htmlDoc) {
  long nId = 0;
  Node* pParent = new Node("", NULL, NULL, -100);
  Node* root = pParent;
  long idx = 1;
  Node* topOfStackNode = NULL;
  bool prevTagClosed = false;
  bool createNode = false;
  string tag;
  gNode[0] = pParent;
  while (idx < htmlDoc.size()) {
    if (htmlDoc[idx] == '/') {
      int i = idx + 1;
      while (htmlDoc[i] && htmlDoc[i] != '>') i++;
      PopFromStack(&topOfStackNode);
      prevTagClosed = true;
      idx = i + 2;
    } else {
      Node* currentNode = NULL;
      int j = idx + 1;
      while (htmlDoc[j] && htmlDoc[j] != '/' && htmlDoc[j] != '>') j++;
      tag = htmlDoc.substr(idx, j - idx);
      nId += 1;
      long tagId;
      if (g_pHashTable->contains(tag) == false) {
        g_pHashTable->put(tag);
      }
      tagId = g_pHashTable->get(tag);
      currentNode = new Node(tag, NULL, NULL, tagId);
      gNode[++gNodeCount] = currentNode;
      PushToStack(currentNode);
      if (prevTagClosed) {
        topOfStackNode->nextSibling = currentNode;
        pParent = currentNode;
        prevTagClosed = false;
      } else {
        pParent->firstChild = currentNode;
        pParent = pParent->firstChild;
      }
      if (htmlDoc[j] == '/') {
        idx = j;
        continue;
      } else {
        idx = j + 2;
      }
    }
  }
  return root;
}
void fillQueryArray(string query) {
  int index = 0;
  int tagIndex = 0;
  {
    if (gQuery) {
      delete[] gQuery;
      gQuery = NULL;
    }
  };
  {
    if (lQuery) {
      delete[] lQuery;
      lQuery = NULL;
    }
  };
  gQuery = new string[MaxQueryCount];
  lQuery = new long[MaxQueryCount];
  while (index < query.size()) {
    if (query[index] == ' ') {
      tagIndex += 1;
    } else {
      gQuery[tagIndex] += query[index];
    }
    index += 1;
  }
  gQTagCount = tagIndex + 1;
  for (int i = 0; i < gQTagCount; i++) {
    if (g_pHashTable->contains(gQuery[i])) {
      lQuery[i] = g_pHashTable->get(gQuery[i]);
    } else {
      lQuery[i] = -1;
    }
  }
}
long PreOrder(Node* apRoot, int aPos) {
  long sum = 0;
  int savePos = aPos;
  if (apRoot == NULL) return 0;
  if (apRoot->tagId == lQuery[aPos]) {
    if (aPos == gQTagCount - 1) {
      sum = 1;
    } else
      aPos++;
  }
  return sum + PreOrder(apRoot->firstChild, aPos) +
         PreOrder(apRoot->nextSibling, savePos);
}
string readHtmlDoc() {
  char sHtmlDoc[1000010] = {0};
  string htmlDoc;
  cin.getline(sHtmlDoc, 1000010);
  for (long i = 0; sHtmlDoc[i]; i++) {
    htmlDoc += sHtmlDoc[i];
  }
  return htmlDoc;
}
int readn() {
  int n = 0;
  char snumber[4] = {0};
  cin.getline(snumber, 4);
  n = atoi(snumber);
  return n;
}
string readQuery() {
  string query;
  int j = 0;
  char ch = 0;
  do {
    ch = getchar();
    if ((ch == '\r') || (ch == '\n')) {
      break;
    }
    query += ch;
    ++j;
  } while (j < MaxQueryCount);
  return query;
}
int main() {
  Node* root = NULL;
  int n = 0;
  string htmlDoc;
  string query;
  g_pHashTable = new HashTable(100);
  if (g_pHashTable == NULL) {
    return -1;
  }
  htmlDoc = readHtmlDoc();
  root = BuildNaryTree(htmlDoc);
  n = readn();
  for (int i = 0; i < n; i++) {
    query = readQuery();
    fillQueryArray(query);
    cout << PreOrder(root, 0) << endl;
    {
      if (gQuery) {
        delete[] gQuery;
        gQuery = NULL;
      }
    };
    {
      if (lQuery) {
        delete[] lQuery;
        lQuery = NULL;
      }
    };
  }
  Node* pNode = NULL;
  for (int iLoop = gNodeCount; iLoop >= 0; iLoop--) {
    {
      if (gNode[iLoop]) {
        delete gNode[iLoop];
        gNode[iLoop] = NULL;
      }
    };
  }
  {
    if (g_pHashTable) {
      delete g_pHashTable;
      g_pHashTable = NULL;
    }
  };
  return 0;
}
HashTable::HashTable(long aSize) {}
HashTable::~HashTable() { mLookupTable.clear(); }
void HashTable::put(string aTag) {
  pair<string, long> item;
  item.first = aTag;
  item.second = mLookupTable.size();
  mLookupTable.insert(item);
}
bool HashTable::contains(string aTag) {
  bool isAvailable = true;
  std::unordered_map<string, long>::iterator it = mLookupTable.find(aTag);
  if (it == mLookupTable.end()) {
    isAvailable = false;
  }
  return isAvailable;
}
long HashTable::get(string aTag) {
  long tagIndex = -1;
  std::unordered_map<string, long>::iterator it = mLookupTable.find(aTag);
  if (it == mLookupTable.end()) {
    return tagIndex;
  }
  tagIndex = it->second;
  return tagIndex;
}
void HashTable::remove(string aTag) {
  std::unordered_map<string, long>::iterator it = mLookupTable.find(aTag);
  if (it == mLookupTable.end()) {
    return;
  }
  mLookupTable.erase(it);
}
long HashTable::size() { return mLookupTable.size(); }