Prime Factor Queries

You are given a positive integer ( n ) and a sequence of queries. There are three types of queries:

1. Type 1: Given an integer ( k ), determine the maximum exponent ( a ) such that ( k^a ) divides ( n ). That is, output the exponent of ( k ) in the prime factorization of ( n ). If ( k ) does not divide ( n ), output 0.

2. Type 2: Given an integer ( k ), output the smallest prime number ( p ) satisfying ( p \ge k ) and with the following rules:

   • If ( k \le 2 ), return ( 2 ) if ( n ) is even; otherwise, return ( 3 ).
   • Otherwise, starting from the smallest odd number ( \ge k ), check each odd number: if it is prime and divides ( n ), return it. If no suitable prime is found while checking numbers up to ( \sqrt{n} ), then return ( n ).

3. Type 3: Given an integer ( k ), if ( k ) divides ( n ), let ( m = n/k ) and output the number of distinct prime factors of ( m ). Otherwise, output 0.

Input Format:

• The first line contains the integer \( n \).
• The second line contains an integer \( q \), the number of queries.
• Then \( q \) lines follow, each containing two space‐separated integers \( t \) and \( k \), where \( t \) is the query type (either 1, 2, or 3) and \( k \) is the associated parameter.

Output Format: For each query, print the corresponding answer on a new line.

Example:

Input:
1000
3
1 2
2 3
3 5

Output:
3
5
2

Explanation:

• Query 1: \( n = 1000 = 2^3 \times 5^3 \). The exponent of 2 is 3.
• Query 2: For \( k = 3 \) (and since 3 > 2), we check odd numbers starting at 3. The smallest odd prime that divides 1000 is 5.
• Query 3: For \( k = 5 \), since 5 divides 1000, consider \( 1000/5 = 200 \). The distinct prime factors of 200 (\( 2 \) and \( 5 \)) count to 2.

inputFormat

The input starts with a positive integer \( n \) on the first line. The second line contains an integer \( q \), the number of queries. Each of the following \( q \) lines contains two space-separated integers \( t \) and \( k \), where \( t \) indicates the query type (1, 2, or 3) and \( k \) is the parameter for that query.

outputFormat

For each query, output the answer on a separate line. No extra spaces or characters should appear in the output.

## sample

1000
3
1 2
2 3
3 5

3
5
2

</p>