Dividing DNA

문제

At the Bacteria And Protein Centre, you own a large collection of DNA. In fact, new strands of DNA come in all the time. To organise the vast amount of data, you identify each piece by its unique substrings: substrings that do not already occur in the database.

Your database can quickly determine whether a given piece of DNA occurs as a substring in the database or not. Naturally, if a certain DNA string is found in the database, it also contains all its substrings.

You now want to determine the uniqueness of a given piece of DNA: the maximal number of disjoint substrings it contains that are absent from the database.

You are given the length $nn$ of the query string $q_1\dots q_{n}q\_1\backslash dots\; q\_n$, and you can repeatedly ask the database whether it contains the substring $q_i\dots q_{j-1}q\_i\backslash dots\; q\_\{j-1\}$.

As an example, consider the first sample interaction. In this case, the database contains strings "TGC" and "CT", and the query string is "CTGCAA". It has uniqueness $33$, because it can be split into the new substrings "CTGC", "A", and "A". The new substring "CTGC" cannot be split up further: for example, the subdivision "CT" and "GC" is not allowed, because both substrings occur (possibly as substrings) in the database. Note that the actual characters in the string are not used in the interaction.

You may use at most $2n2n$ queries to the database.