Enchanted Necklace

Many Thanks to Clive Fraser for this curious puzzle and accompanying story!

Grunwald the Goblin has a lucrative business creating and selling enchanted necklaces. The wearer of one of these necklaces is guaranteed to have good health and prosperity. One end of the necklace clasp is made of gold and the other end is made of silver. Between the two ends of the clasp there is a line of jewels. Some of these are rubies; the others are emeralds. The order of the jewels is very important. In particular, no two necklaces can have the same order of these jewels. One of the properties needed for the enchantment is that the necklaces must be unique.

A second, more complicated requirement, for the enchantment to work is that the line of jewels can not be any repeated sequence of a shorter line. If we use E and R to represent emeralds and rubies, and G and S to represent the gold and silver ends of the clasp, we can use strings of letters to represent the completed necklace. First note that GEERS and SEERG are different necklaces because the two ends of the clasp are in different places with respect to the jewels. However, GEERS and SREEG are the same necklace (just picked up and put down in a different way).

We will now ignore the clasp in order to illustrate the restriction on having repeated sequences of jewels within the necklace. EEEE is not allowed because it is made up of 4 repetitions of E. ERERER is not allowed because it is made up of 3 repetitions of ER. However ERERERRE is allowed because the full string is not made up of multiple copies of any single shorter string. RERRRERRRERR is not allowed because it is made up of 3 copies of RERR.

In this problem you will be given the numbers of emeralds and rubies that Grunwald has used to create a necklace. You are asked to find the number of different enchanted necklaces which he could have created from these jewels.

If we consider a very small example where Grunwald uses 2 emeralds and 2 rubies we find that there are just 4 enchanted necklaces which can be made. These are:

GEERRS  GRREES  GREERS  GERRES

The number of enchanted necklaces increases rapidly as the number of jewels increases. Because of this you are asked to give your answer modulo 1000000007 (10^9 +7). The total number of jewels in the necklace will not exceed 2 million.

Input/Output description: The first line of the input data will contain a single integer N, the number of puzzles to solve. N lines will follow. Each of these contains two space-separated integers E and R for the number of emeralds and the number of rubies. For each puzzle, you need to determine the number of different enchanted necklaces which can be made, each one using all of these jewels. Give your answers modulo 1000000007 and combine these into a single string, separated by single spaces.

Example:

input:
4
2 2
945 630
6069 6069
826500 1157100

answer:
4 62993040 931644031 604535237