Nimbus, the techical festival of NIT Hanirpur is coming and thus Arun, the core-cordinator of departmental team of CSE, decided a conduct a game. In this game, the participant will be given a natural number N and will be asked T questions of form Type K.

Here Type denotes the type of question asked and K denotes a natural number.

If Type=1, the participant must find the number of natural numbers which is divisor of both N and K.

If Type=2, the participant must find the number of natural numbers which is divisor of N and is divisible by K.

If Type=3, the participant must find the number of natural numbers which is divisor of N and is not divisible by K.

As it will be very difficult for Arun to tell manually whether the asnwer given by participant is correct or not. So, he decided so write a code for it. As Arun is very busy for NIMBUS preparations, he has given this task to you.

INPUT

The first line of input contains 2 integers N and T, denoting the natural number and the number of questions asked respectively. The next T lines contains 2 integers Type and K, denoting the Type of question asked and the natural number respectively.

OUTPUT

For each test case output a single integer (one per line), that is the answer to the question.

CONSTRAINTS

1<=N<=10^12

1<=T<=5*10^5

1<=Type<=3

1<=K<=10^12