There are $100\,000$ countries on a beautiful continent, labeled from $1$ to $100\,000$. The economy is highly developed, with countless accounting offices, and each country has one bank. A leader of a large corporation opened accounts in these $100\,000$ banks, depositing $3$ units of currency in each. Being extremely frugal, he frequently sends his subordinate, GFS, to audit the deposits of some banks or to change the deposit amount in a specific bank. The summation ($\sum$) operation in this village is equivalent to our multiplication ($\prod$) operation, meaning the total deposit when the leader opened the accounts was $3^{100\,000}$. The currency denominations issued here are the smallest $60$ prime numbers ($p_1 = 2, p_2 = \dots, p_{60} = 281$). Anyone's wealth can only be represented by these $60$ basic denominations; that is, if a person's wealth is $fortune$ (a positive integer), then $fortune = p_1^{k_1} * p_2^{k_2} * \dots * p_{60}^{k_{60}}$.

The leader is accustomed to taking the deposits from a range of consecutively numbered banks to an accounting office for auditing. To prevent GFS from colluding with the accounting offices, he does not choose the same office every time. GFS has followed the leader for many years and has figured out the leader's method for choosing an office. If the leader chooses to audit the bank deposits in the range $[a, b]$, he first calculates the product of the deposits in $[a, b]$ (denoted as $product$), and then chooses an office from the range $[1, product]$ to audit the deposits, in order to verify if his own calculation is correct and also to check if there is any collusion between the office and GFS. GFS discovered that if the number of an accounting office, $number$, is "in conflict" with $product$, the leader will never choose this office. What does it mean to not be in conflict with $product$? If there exist integers $x, y$ such that $number * x + product * y = 1$, then we say $number$ is not in conflict with $product$, meaning this office could potentially be chosen by the leader. When the leader earns more money, he changes the deposit in a certain bank, so the $product$ calculated for the same range at different times may be different. Furthermore, the leader will never have a total deposit in a single bank exceeding $1\,000\,000$.

Now, GFS knows the leader's plan for auditing and changing deposits in advance. He wants you to tell him how many accounting offices are available for the leader to choose from each time he audits the deposits. Of course, this value can be very large, and GFS only wants to know the $answer$ modulo $19961993$.

Input

The first line contains an integer $x$, representing the total number of audit and deposit change operations.

The next $x$ lines each contain three integers $a_i, b_i, c_i$. If $a_i = 0$, it indicates an audit operation; the leader audits the bank deposits from $b_i$ to $c_i$, and you need to calculate the $answer$ GFS wants for this record. If $a_i = 1$, it indicates a deposit change; you need to change the deposit of bank $b_i$ to $c_i$, and no calculation is required for this record.

Output

Output several lines, each containing one integer, representing the $answer$ for those years.

Examples

Input 1

6
0 1 3
1 1 5
0 1 3
1 1 7
0 1 3
0 2 3

Output 1

18
24
36
6

Note

Initially, the deposit in each country is $3$; The $product$ for $1$ to $3$ is $27$, and there are $18$ numbers in $[1, 27]$ that are not in conflict with $27$; The deposit in $1$ becomes $5$; The $product$ for $1$ to $3$ is $45$, and there are $24$ numbers in $[1, 45]$ that are not in conflict with $45$; The deposit in $1$ becomes $7$; The $product$ for $1$ to $3$ is $63$, and there are $36$ numbers in $[1, 63]$ that are not in conflict with $63$; The $product$ for $2$ to $3$ is $9$, and there are $6$ numbers in $[1, 9]$ that are not in conflict with $9$.

Constraints

$20\%$ of the data satisfies: $x \le 10000$, and when $a_i = 0$, $0 \le c_i - b_i \le 100$; each $product \le 10^{18}$; $30\%$ of the data satisfies: $x \le 50000$; when $a_i = 0$, $0 \le c_i - b_i \le 10000$; $50\%$ of the data satisfies: $x \le 100000$; when $a_i = 0$, $0 \le c_i - b_i \le 100000$; The above data sets are disjoint, $20\% + 30\% + 50\% = 100\%$, and it is guaranteed that the requirements of the problem are met.