Smallest possible poll sample

Given a percentage printed to three decimals, find the smallest sample size n for which some count k rounds to that percentage.

Medium5MathBrute forceNo attempts yetTime limit1sMemory limit256 MB

Problem

A news story that quotes a poll usually prints a percentage instead of the raw vote counts. From that percentage alone, work out how small the sample could have been.

The question takes yes or no as its only answers. If kk of the nn people in the sample answered yes, then 0kn0 \le k \le n, and the story prints 100kn\frac{100k}{n} rounded at the fourth decimal place. When the fourth decimal digit is 5 or more the third decimal place goes up, otherwise everything from the fourth digit on is dropped.

Given the percentage printed in the story, find the smallest possible value of nn.

Input

The first line contains the number of test cases TT.

Each of the next TT lines contains one printed percentage, written with exactly three digits after the decimal point. Every value is between 0.0000.000 and 100.000100.000.

Output

For each test case, print the smallest possible sample size on its own line.