408160: GYM103034 C Two Hashes

You have learned about polynomial hashing recently. Firstly, you choose a prime $$$MOD$$$ and a large enough integer $$$C$$$. Then, for every string $$$s = s_{n-1}s_{n-2}\cdots s_{1}s_{0}$$$ of lowercase English letters, you hash it to the value $$$\displaystyle\sum_{i=0}^{n-1}val(s_{i}) \cdot C^{i} \pmod{MOD}$$$, where val(a) = 1, val(b) = 2, ..., val(z) = 26.

You tested this algorithm by hashing $$$10000$$$ random strings of length $$$50$$$. You choose $$$MOD = 10^{9}+9$$$ because that's your favourite prime. However, you realized halfway that you are not using the same value of $$$C$$$ to hash every string! More precisely, for every string, you chose either $$$C = 115381398$$$ or $$$C = 276147934$$$ uniformly randomly and hash the string using this value of $$$C$$$.

You wonder if there is a way to tell which value of $$$C$$$ you used to hash each string. Can you solve this task?

Sample implementation of the hash function in C++: https://ideone.com/xYGvdD

The first line of input contains a single integer, $$$t$$$ ($$$t = 10000$$$).

Each of the next $$$t$$$ lines contain a single integer, $$$x_i$$$ ($$$0 \le x_i < 10^{9}+9$$$), denoting the hash value of the $$$i$$$-th string.

There are more lines in the input but they are meant to be used for the checker only and it is guaranteed that you do not need to use them to get full score.

Output $$$t$$$ lines, each containing a single integer. If you think $$$x_i$$$ is generated by $$$C = 115381398$$$, output $$$1$$$ on the $$$i$$$-th line. Otherwise, output $$$0$$$ on the $$$i$$$-th line.

You get more points if you get more testcases correct. You will get positive score if and only if you get at least half the testcases correct.

2
923051192
596459381

1
0

Note that the sample shown is not a valid input based on the constraints, because $$$t \neq 10000$$$.