On the official website of Berland, each account has two parameters: username and ID.

Username is a string consisting of lowercase Latin letters and/or digits, which contains at least one letter. For example, user0, 1fox1, zzzz are correct usernames, but 1337 and User22 are not.

The ID of the account for a given username is generated as follows: a positive integer without leading zeroes is appended to the end of the username. For example, the ID user0125 can be generated by the following usernames: user012, user01, user0; but neither by user nor us.

You are given a string $$$s$$$ — a valid ID. Your task is to determine any valid username that can generate the given ID. If there are several correct usernames, you can print any of them.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

The only line of each test case contains a string $$$s$$$ ($$$2 \le |s| \le 50$$$), consisting of lowercase Latin letters and/or digits.

Additional constraint on input: there is at least one valid username that can generate the given ID.

Output

For each test case on a separate line, print a string — any valid username that can generate the given ID. If there are multiple correct usernames, you can print any of them.

Username

Examples