Metro

In a city far away there is a metro line consisting of N stations, numbered 1 to N. The metro is a straight line, i.e. from the station i you can directly reach stations numbered i-1 and i+1 (from the first station you can only reach the second one and similarly, from the N-th station you can only reach station no. N-1). Each station has its passcode, a positive integer which can change from day to day. If we have a ticket numbered k, we can reach some station (from either side) only if k divides the passcode of that station. We are interested in the number of different stations we can visit starting from a specific station and with a specific passcode.

More formally, you are given Q queries of one of two different kinds:

1 i x - change the passcode of the i-th station to x,
2 i k - we want to know the number of different stations you can visit starting from the i-th station with a ticket numbered k.

You should print the answers to all type 2 queries. Our ticket number will always divide the passcode of the starting station.

Explanation for the sample:

If we are at the station 3 (with a passcode 20) and we have a ticket number 5, we can visit three stations - 2, 3 and 4. Although 5 divides the entry code of the station 6, we cannot reach it because 5 doesn't divide the passcode of the fifth station - 19. In the next query we start from station number 4, and we cannot go anywhere else. After changing the passcode of the fifth station, we can visit 5 stations starting from the station 3 with a ticket number 5 - stations numbered 2, 3, 4, 5 and 6.

Remark.

20% of the test cases will satisfy Q ≤ 1.000. In 40% of the testcases we will always have the same ticket i.e. all type 2 queries will have the same number k. Such testcases will have odd Q and all others will have even Q).