Prime words

Problem code: C3

All submissions for this problem are available.

In the magic land of Mathtopia, the words of the language are written only using two symbols: ones and zeros.

A given word w is called "prime" if it cannot be written in the form of the concatenation of several copies of some shorter word. So, for example the words '100', '1100', and '001100' are prime, while the words '0101', '100100', '1111', and '101010' are not prime.

Your task is to calculate the number of prime words which can be built from exactly a ones and b zeros.

Input

t - the number of test cases. For each test case, two integers: 1<=a<=109, 1<=b<=109.

Output

For each test case, output the required answer modulo 531169.

Example

Input:
1
2 2

Output:
4

Explanation: the 4 words from the example are:
'0011','1100','0110','1001'.

Date: 2009-04-20
Time limit: 1s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

sreeni @ 4 May 2009 05:03 PM

Here 2 is the min length of a word?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions