Doraemon's Number Game II

Time Limit: 2 Seconds
Memory Limit: 65536 KB

Doraemon plays game with Nobita one day.

Doraemon gives a number *x* with length *n* in base *B*, then Doraemon removes one digit from number *x*, the location of this digit is from *s* to *t* (3 ≤ *s* ≤ *t* ≤ n). We call the leftmost digit of *x* the first digit, the rightmost digit of *x* the nth digit. After removing one digit, we get a number *y* in base *B*. Nobita should answer the number of possible values of *x* which follows the constraint that there exists a corresponding *y* after removing a digit so that *x* is divisible by *y*.

Nobita also wants Doraemon to solve a similar problem. But Nobita is not good at arithmetic, he can only remove the first digit of *x* to form a new number *y*. Then Doraemon should answer the number of possible values of *x* whose corresponding *y* is a divisor of *x*.

#### Input

Input contains multiple cases (1 ≤ *case_num* ≤ 2000). Process to the end of file. Each case gives the length of the number *n*(3 ≤ *n* ≤ 100), base *B*(2 ≤ *B* ≤ 32), start position *s* and end position *t*(3 ≤ *s* ≤ *t* ≤ *n*) in a single line separated with a single space.

#### Output

Output contains two numbers separated by a single space, the first is Doraemon's answer, and the second number is Nobita's answer.

#### Sample Input

3 10 3 3

#### Sample Output

90 117

Author:

**QU, Zhe**
Contest:

**ZOJ Monthly, December 2010**
Submit
Status