from collections import Counter
from math import floor, ceil, log
from heapq import heapreplace, heappush
import time


class TreeIndex:
    CACHESIZE = 65535

    class Node:
        __slots__ = ('level', 'keys', 'values', 'keylen')

        def __init__(self, level):
            self.level = level
            self.values = []
            self.keys = {}
            self.keylen = 2 ** self.level

        def add(self, text, value):
            if len(text) == 0:
                self.values.append(value)
                return self
            pre = text[:self.keylen]
            post = text[self.keylen:]
            if pre not in self.keys:
                self.keys[pre] = self.__class__(self.level+1)
            return self.keys[pre].add(post, value)

        def find(self, text):
            if len(text) == 0:
                return self
            pre = text[:self.keylen]
            post = text[self.keylen:]
            if pre in self.keys:
                return self.keys[pre].find(post)
            else:
                return None

        def __contains__(self, text):
            if len(text) > self.keylen:
                pre = text[:self.keylen]
                post = text[self.keylen:]
                return (pre in self.keys and post in self.keys[pre])
            else:
                return any(key.startswith(text) for key in self.keys)

        def __str__(self):
            return ('(' + ','.join(["{}->{}".format(k, v)
                                   for k, v in self.keys.items()]) + ')')

    def __init__(self, text):
        self.text = text
        self._init_cache()
        self._keylen()
        self._create_index()

    def _keylen(self):
        chars = Counter(list(self.text))
        ent = 0.0
        total = len(self.text)
        base = len(chars) + 1
        for c, cnt in chars.items():
            p = cnt / total
            ent -= p * log(p, base)
        self.keylen = max(2 ** ceil(10 * (1 - ent)) - 1, 3)

    def _create_index(self):
        self.tree = self.Node(0)
        length = len(self.text)
        for i in range(length):
            self.add(self.text[i:i+self.keylen], i)

    def _init_cache(self):
        self._cache = {}
        self._cacheq = []

    def _set_cache(self, text, node):
        if text not in self._cache:
            if len(self._cacheq) > self.CACHESIZE:
                _, txt = heapreplace(self._cacheq, (time.clock(), text))
                del self._cache[txt]
            else:
                heappush(self._cacheq, (time.clock(), text))
            self._cache[text] = node

    def _get_cache(self, text):
        if text in self._cache:
            return self._cache[text]
        else:
            return None

    def index(self, text):
        node = self._get_cache(text)
        if node is None:
            node = self.tree.find(text)

        if node is None:
            return []
        else:
            self._set_cache(text, node)
            return node.values

    def add(self, text, value):
        node = self._get_cache(text)
        if node is None:
            node = self.tree.add(text, value)
            self._set_cache(text, node)
        else:
            node.add('', value)

    def match(self, search_text):
        def _match_partial(lo, hi):
            split = self.keylen
            if search_text[lo+split:hi] in self.tree:
                for i in self.index(search_text[lo:lo+split]):
                    if (self.text[i+split:i+hi-lo]
                            == search_text[lo+split:hi]):
                        yield i

        def _match(lo, hi):
            length = hi - lo

            if length == self.keylen:
                return (i for i in self.index(search_text[lo:hi]))
            elif length < self.keylen*2:
                return _match_partial(lo, hi)

            mid = lo + length // 2
            pre = _match(lo, mid)
            post = _match(mid, hi)

            return _merge(pre, post, mid-lo)

        def _merge(idx1, idx2, shift):
            i2 = next(idx2)
            for i1 in idx1:
                while i1 + shift > i2:
                    i2 = next(idx2)
                if i1 + shift == i2:
                    yield i1

        length = len(search_text)
        if length < self.keylen:
            return search_text in self.tree

        # align by key length
        k = floor(log(length/self.keylen, 2))
        b = self.keylen * 2**k
        if length - self.keylen < b < length and k > 0:
            b = self.keylen * 2**(k-1)

        try:
            if b + self.keylen < length:
                match = _merge(_match(0, b), _match(b, length), b)
            else:
                match = _match(0, length)
            next(match)
            return True
        except StopIteration:
            return False


def run():
    s1 = input()
    n = int(input())

    index = TreeIndex(s1)
    for _ in range(n):
        s2 = input()
        if index.match(s2):
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()



Measured memory_bytes: 86428