Little H is a collector who loves collecting positive integers. Little H has a habit: before going to sleep, he calculates how many pairs of positive integers among all the positive integers he has collected have a greatest common divisor (GCD) exactly equal to $k$.

Every day, Little H might collect a new positive integer, or he might discard a positive integer for some reason. This means the set of positive integers he has collected is constantly changing, and the value calculated before sleep might be different each day. However, $k$ never changes. At the same time, Little H guarantees that $k$ is either $1$ or a prime number.

Little H wants to know, after each time he collects a new positive integer or discards a positive integer, how many pairs of positive integers have a greatest common divisor equal to $k$.

Input

The first line contains two integers $n$ and $k$. The next $n$ lines each contain two integers $a$ and $b$.

• If $a = 0$, it means Little H discards a positive integer $b$ that he has collected. If Little H does not currently have $b$ in his collection, it might be that Little H misremembered, so no changes need to be made.
• If $a = 1$, it means Little H collects a new positive integer $b$. Note that Little H can collect many identical positive integers.

Output

Output $n$ lines, each containing one integer, representing the answer after each discard or collection operation.

Constraints

Let $z$ be the maximum value among all positive integers collected by Little H. For all data, $1 \le k \le z$.

Examples

Input 1

5 2
1 2
1 4
0 2
1 2
1 2

Output 1

0
1
0
1
3

Input 2

8 3
1 3
0 3
0 3
1 3
1 6
1 9
1 12
1 2

Output 2

0
0
0
0
1
3
5
5