You have 105 bags enumerated from 1 to 105. All bags are initially empty. You have to perform Q operations. Each operation is of one of the following types:
-
Type 1: You are given a number X. You have to find all the prime factors of X and add 1 coin to all the prime factor numbered bags.
-
Type 2: You are given two integers L and R. You need to answer the number of coins you have in bags numbered from L to R.
Input Format
First line of the input contains a single integer Q denoting the number of operations.
Then, Q lines follow where each line is an operation of either Type 1 or Type 2.
- Type1 query have two space separated integers 1, X.
- Type2 query have three space separated integers 2, L, R.
Output Format
Print answer for every type 2 query in a separate line.
Constraints
- 1≤Q,X≤105
- 1≤L≤R≤105
First 6 is added hence coins are added to bags 2 and 3.
In query 1 to 5 , the number of coins are 2(at 2 and 3).
Then 5 is added, hence coins are added to bags 5.
In query 2 to 5 , the number of coins are 3(at 2 ,3 and 5).
