Lucky Tickets

[Deleted user]

Tickets in public transport systems have unique numbers. We have a funny superstition about them:

If the sum of digits in the first half of a ticket's number equals the sum of digits in the second half, then such a ticket is considered "Lucky" . One should immediately recall some long-held dream and eat this ticket, and, surely, the dream will come true!

The ticket number is split into halves of equal length, of course. If the number contains an odd amount of digits, then the middle digit is simply ignored. So, 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 leading zeroes, for example 6-digit numbers start from 000000, 000001 and end with 999998, 999999.

We are going to undertake a great reform - the Ministry of Transport wants to create tickets with a new number format. The new format 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 many "lucky tickets" exist for given pair of N and B. You may safely assume that numbers with larger values 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