H. Plantery Observations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the 4th century BC, Edwin observes a point in the sky and notices that all the planets in their solar system cross by this point at various points in time. Every time he sees a planet cross by this point, he logs this in his journal.

Being smart, Edwin decides to invent the computer and wants to write a program to help him determine the smallest period that could explain his observations $$$O$$$ in the sky.

There are two kinds of queries Edwin wants to give the computer:

  • 0 s where Edwin writes down a string $$$s$$$ of $$$len(s)$$$–these observations which get appended to a string $$$O$$$
  • 1 Edwin wants to know the smallest period that could explain his observations in the sky.

It is guaranteed that $$$N\cdot \sum len(s)\leq 2\cdot 10^5$$$ and the first query is of type $$$0$$$.

Input

The first line will contain $$$N (1\leq N\leq 10^3)$$$, the number of queries.

The next $$$N$$$ lines will either contain a query either of type 0 s or 1.

Output

For each query of type 1, print out the smallest period that could explain his observations in the sky on a new line.

Examples
Input
2
0 abcabca
1
Output
3
Input
4
0 ab
1
0 cabca
1
Output
2
3