Smallest possible poll sample

Time limit1sMemory limit256 MB

Summary

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

Level: Medium5 of 10
Topics: Math, Brute force
Solved: No attempts yet

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 $k$ of the $n$ people in the sample answered yes, then $0 \le k \le n$ , and the story prints $\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 $n$ .

Input

The first line contains the number of test cases $T$ .

Each of the next $T$ lines contains one printed percentage, written with exactly three digits after the decimal point. Every value is between $0.000$ and $100.000$ .

Output

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

Examples3

Example 1
Input
```
3
0.001
50.000
15.000
```
Expected output
```
66667
2
20
```
Example 2
Input
```
2
0.000
100.000
```
Expected output
```
1
1
```

Example 3

Input

Expected output