Little Alice has a lot of color beads. She can pick several of them and string them into necklace.
She found that with only
2 beads of only
2 colors (say,
green) three different necklaces could be
created - for example:
red-red red-green green-green
3 beads of
2 colors it is possible to make
The image above shows
6 variants made of
4 two-color beads.
You see, since the necklace have ends of the string tied together, there are far less variants than for linear strings of beads - i.e. while strings like
are different before their ends are tied, they nevertheless produce the same necklace.
However we differ necklaces which are "mirror" of each other (since it is not possible to convert one into another simply by rotating it around the neck). For example
is not the same as
If we do not distinguish mirrored necklaces, they are usually called bracelets. However this does not change
problem significantly so we do not include this minor implication. (so for example with
6 beads of
2 colors we
14 necklaces but only
Input data contains the number of testcases in the first line.
Next lines contain a pair of values each - the number of colors
B - and the amount of beads to form necklace
Answer should contain the number of different necklaces which could be made in each case.
input data: 3 2 6 9 4 12 1 answer: 14 1665 12
B <= 12 and
N (depending on it) would be such that the result will not exceed few millions.