CF1766B Notepad#

You want to type the string $ s $ , consisting of $ n $ lowercase Latin letters, using your favorite text editor Notepad#. Notepad# supports two kinds of operations: - append any letter to the end of the string; - copy a continuous substring of an already typed string and paste this substring to the end of the string. Can you type string $ s $ in strictly less than $ n $ operations?

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the string $ s $ . The second line contains a string $ s $ , consisting of $ n $ lowercase Latin letters. The sum of $ n $ doesn't exceed $ 2 \cdot 10^5 $ over all testcases.

For each testcase, print "YES" if you can type string $ s $ in strictly less than $ n $ operations. Otherwise, print "NO".

In the first testcase, you can start with typing "codef" ( $ 5 $ operations), then copy "o" ( $ 1 $ operation) from an already typed part, then finish with typing "rces" ( $ 4 $ operations). That will be $ 10 $ operations, which is not strictly less than $ n $ . There exist other ways to type "codeforces". However, no matter what you do, you can't do less than $ n $ operations. In the second testcase, you can type "labac" ( $ 5 $ operations), then copy "aba" ( $ 1 $ operation), finishing the string in $ 6 $ operations.