# Necklace Count

Problem #111

Tags: mathematics puzzle combinatorics

Who solved this?

It is a classical puzzle. Martin Gardner mentions that it is found at "one of puzzle collections by Henry E Dudeney", though I failed to trace the original.

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, `red` and `green`) three different necklaces could be created - for example:

``````red-red
red-green
green-green
``````

With `3` beads of `2` colors it is possible to make `4` necklaces. 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

``````red-green-red
red-red-green
``````

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

``````red-red-green-red-green-green
``````

is not the same as

``````red-red-green-green-red-green
``````

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 can make `14` necklaces but only `13` bracelets).

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 `N`.
Answer should contain the number of different necklaces which could be made in each case.

Example:

``````input data:
3
2 6
9 4
12 1

Limits: `B <= 12` and `N` (depending on it) would be such that the result will not exceed few millions.