Invariant Polynomials

Time Limit: 1 Second    Memory Limit: 32768 KB

Consider a real polynomial P(x, y) in two variables. It is called invariant with respect to the rotation by an angle alpha if

P(xcosa - ysina, xsina + ycosa) = P(x, y)

for all real x and y.

Let's consider the real vector space formed by all polynomials in two variables of degree not greater than d invariant with respect to the rotation by 2pi/n. Your task is to calculate the dimension of this vector space.

You might find useful the following remark: Any polynomial of degree not greater than $d$ can be uniquely written in form

P(x, y) = sum{aijx^iy^j} where i, j >= 0 and i + j <= d

for some real coefficients aij.

Input

The input contains two positive integers d and n separated by one space. It is guaranteed that they are less than one thousand.

Output

Output a single integer M which is the dimension of the vector space described.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input

2
 
1 1

2 2

Sample Output

3
 
4

Submit

Source: Northeastern Europe 2003, Northern Subregion