Skip to content

UKSPC Practice Problems » The Traveling Author

driver.c, driver.cpp, or
standard input
standard output

As a poor traveling author you often find yourself in foreign lands trying to get published to raise enough money to travel to the next foreign land so you can continue on your search for the elusive mayfly of love. You often question your bohemian lifestyle and daily regret not becoming an engineer, today is no exception. This morning you woke up to find that you had fallen off of the train you were sleeping in and were in a strange land indeed. The people were normal enough but their local publisher charges the wackiest rates and their currency, the ajat, is absurdly inflated. A sign hanging in the window reads:

Get your book published here today!! Only X ajat's for every digit of every page number printed (no leading zeros). Exact change only!! X and the number of pages are positive, non-zero integers; all books start at page 1.

The lady at the desk gives you the following examples: for a book with eight pages numbered 1 through 8, we have to use 8 digits. At 8 ajats per digit, our total cost would be 64 ajats. For a book with eleven pages numbered 1 through 11, we have to use 13 digits. So at 7 ajats per digit, our total cost would be 91 ajats. After visiting the bank to exchange all of your money for ajats you have N ajats to spend. You must now figure out how many pages you can print for your N ajats. Too bad you arenít a programmer...

The input is consists of: a single number L, followed by a newline, followed by L lines consisting of a number N, a space, and another number X. Your output should be L lines long; on each line, there should be one number corresponding to the number of pages you can print for each set above. N is your number of ajats and X is the cost of one digit in ajats. If N is not the exact cost of a number of pages, output 0.

Sample Input Sample Output
91 7
64 8
1342344323565545634557 863453434577564
1342348022637014588628 863453434577564
121 11