Bitcash Link to heading

Mr. Satoshi has figured out a machine that literally prints money. However, when he tries to assemble it he cannot crack the final piece of the puzzle. He needs an expert in algorithms and data structures and have come to you for help.

Mr. Satoshi has devised a scheme where each minted coin is signed with a SHA256 hash but he feels like they need more flair than just an ugly hash. “What if they all start with like, fifteen leading 0’s?”.

Each minted coin is stamped with a SHA256 hash for security purposes. To stamp a coin you take the content ID (a random string of up to 1000 characters) and find a value X such that:

>>> SHA256(X) == content_ID
# and
>>> X[:15] == b'0' * 15

X is what Mr. Satoshi calls the “Stampage”.

Input Link to heading

A number N, 1 <= N <= 100000, representing the number of queries to come. Then N lines, each containing a content ID.

Output Link to heading

For each N line in the input, output a valid stampage for that line.

Time Limit: 1 Second