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.
t - the number of test cases. For each test case, two integers: 1<=a<=109, 1<=b<=109.
For each test case, output the required answer modulo 531169.
Input: 1 2 2 Output: 4
Explanation: the 4 words from the example are:
|Time Limit:||0.130208 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, SQL, kotlin, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.