Mount Allison Programming Showdown 2020

Start

2020-03-28 08:00 AKDT

Mount Allison Programming Showdown 2020

End

2020-03-28 13:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -103 days 17:31:02

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Impossible Prices

/problems/impossibleprices/file/statement/en/img-0001.jpg
Image by Ferenz (Shutterstock), Used under license

Dio’s parents have recently retired to a villa in Greece, leaving him in charge of the family business, a home decor store specializing in ancient pottery (and a proud member of ICPC, the International Consortium of Pottery Companies). Dio enjoys interacting with customers, and always experiences a sense of satisfaction when he makes a sale. In idle moments, he often finds himself thinking about recent transactions, and, in particular, about the specific prices that customers have paid. In the midst of such musings, it strikes him that some prices are actually impossible, i.e., there are prices (perfectly sensible-sounding prices) that no customer will ever end up paying. The reason is that although Dio has essentially unlimited discretion in choosing the amount written on the price tag attached to each item in his store, this is the pre-tax price, whereas the actual price that a customer pays for an item is the after-tax price. The difference between the two is what creates the possibility of impossible prices.

Because the monetary system in Dio’s country is based on dollars and cents, a price (pre-tax or after-tax) is always a positive real number with exactly two digits after the decimal point. The tax rate, $T$, which is expressed as a percentage, is fixed by the government. It follows that if $x$ is a pre-tax price, then the resulting after-tax price, $\mathrm{ATP}(x)$, is given by

\[ \mathrm{ATP}(x) = \langle \, x (1 + T/100) \, \rangle \]

where $\langle \ \rangle $ means “round to the nearest cent.” For example, if $x = 2.24$ and the tax rate is $10\% $, then

\[ \mathrm{ATP}(x) = \langle \, 2.24 (1 + 10/100) \, \rangle = \langle \, 2.24 \cdot 1.1 \, \rangle = \langle \, 2.464 \, \rangle = 2.46 \]

However, if $x$ is increased by $1$ cent (the smallest possible increment), then $x = 2.25$ and

\[ \mathrm{ATP}(x) = \langle \, 2.25 \cdot 1.1 \, \rangle = \langle \, 2.475 \, \rangle = 2.48 \]

Notice that $2.47$ was skipped, i.e., $2.47$ is an impossible price when the tax rate is $10\% $.

Given a tax rate, $T$, and a closed interval $[A, B]$, where $A$ and $B$ are prices and $A \leq B$, help Dio determine how many prices in the interval are in fact impossible.

Rounding Rule: If $p$ is a price, then the real numbers that round to $p$ are exactly those that lie in the half-open interval $[p - 0.005, p + 0.005)$.

Input

The first line of input contains an integer, $N$ ($1 \leq N \leq 100$), the number of test cases. This is followed by $N$ lines, one per test case, each of which contains three space-separated real numbers, $A$, $B$, and $T$, where $1 \leq A \leq B \leq 10^{12}$ and $0 \leq T \leq 100$. Every real number will have exactly two digits after the decimal point.

Output

For each test case, output a line containing a single integer: the number of impossible prices in the closed interval $[A, B]$ when the tax rate is $T$.

Sample Input 1 Sample Output 1
2
2.46 2.48 10.00
6.00 9.00 50.00
1
100