Every number greater than 1 is either a prime or a composite. Aman is studying how property of number changes when 1 is added to it. He defines a number as a "good number" if that number retains it's property. Means prime remains prime and composite remains composite.

You will be given an array of N integers . And you will be asked to solve Q queries which are of two types

• 1 x y -> Set arr[x] = y (1 based indexing)
• 2 x y -> Print the number of good numbers in range x to y both inclusive

Input Format

• First line contains N and Q
• Each of the next Q lines contains queries described in above format

Output Format

• Output result for all the queries of 2nd type.

Constraints

• N<=10^6
• 1 < arr[i] <= 10^6
• Q<=10^5
• 1<=L<=R<=N
• 1<=x<=N
• 1 < y <= 10^6

Author : Aayush Kapadia