Lucky Tickets

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 considered "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 117234 or 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 000000, 000001 and end with 999998, 999999.

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 24 digits.

You are to count how much "lucky tickets" exist for given pair of N and 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 N and B each.
Answer should contain the amount of lucky tickets for each case:

Example:

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