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'.

Author: admin
Date Added: 20-04-2009
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


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