Irreducible Fractions

Input: Standard Input

Output: Standard Output

A fraction is irreducible if its numerator and denominator don’t have any common factor greater than 1. For example are all irreducible fractions. But there are some fractions like , which is irreducible for any integer value of n. It is not quite straightforward to identify such fractions.

Now consider the fraction with general form, , where a, b, x, y are always integers satisfying 0 £ x, y £ 10⁷ and (0 £ a, b £ 32000, (a+b) > 0) . If values of a and b are given then we will be able to find some pair of values (x,y) such that for any integer value of n, fraction is irreducible. One possible way of finding some of such pairs (x,y) is by using the theorem “If there exist integers p and q such that rp+sq = 1 (r and s are also integers), then r and s are relatively prime.” So if (an+x) and (bn+y) are relative prime then we can write

(an+x)p + (bn+y)q = 1

=>n(ap+bq) + (px+qy) = 1 …(i)

The relation (i) above can hold for any value of n, if ap+bq=0 and px+qy=1. Given the value of a and b your job is to count how many different (x, y) pairs there are such that there exist integers p, q satisfying ap + bq = 0 and px + qy = 1.

Input

There can be up to 100000 lines of inputs. Each line contains two non-negative integers which denote the value of a and b (0 £ a, b £ 32000, (a+b) > 0) respectively.

Input is terminated by a line containing two zeroes. These two zeroes need not be processed.

Output

For each line of input except the last one, produce one line of output. This line contains an integer P. This P denotes the total number of different pair of integer values for x and y, which ensures that ap+bq = 0 and px+qy = 1, where (0 £ x, y £ 10⁷).

Sample Input Output for Sample Input

100 223

2300 1000

0 0

89686

869565

Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman (Moderator), Rujia Liu