Tickets in public transportation system have unique numbers. We have a funny superstition or omen about them:
If the sum of digits in the first half of number equals to sum of digits in the second half - such ticket is concidered "Lucky" - one should at once recollect some long-wished dream and eat this ticket - then the dream surely will come to reality!
Number is split into halves of equal length, of course. If the number contains an odd amount of digits - the middle
of them is simply ignored. So the numbers like
4493278 are examples of lucky ones:
1 + 1 + 7 = 2 + 3 + 4 = 9 4 + 4 + 9 = 2 + 7 + 8 = 17 (3 is ignored)
Of course the number may have trailing zeroes, for example
6-digit numbers start from
000001 and end
We are going to undertake a great reform - ministry of transportation wants to create tickets with new number format -
it would contain
N digits, each of them in numeral system with base
B. Numeral systems of up to hexadecimal
would be used (i.e.
B <= 16) and numbers could be of up to
You are to count how much "lucky tickets" exist for given pair of
B. You may safely assume that numbers with
great value of
N will use smaller values of
B to simplify the matter for you.
Input data contains the number of test-cases in the first line.
Next lines contain a pair of values
Answer should contain the amount of lucky tickets for each case:
input data: 4 1 5 4 3 5 2 6 10 answer: 5 19 12 55252
If you have found this problem too easy, try an Lucky Tickets Advanced