## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## A Perfectly Balanced String? Solution | Codeforces Problem Solution 2022

B. A Perfectly Balanced String?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let's call a string $s$ perfectly balanced if for all possible triplets $\left(t,u,v\right)$ such that $t$ is a non-empty substring of $s$ and $u$ and $v$ are characters present in $s$, the difference between the frequencies of $u$ and $v$ in $t$ is not more than $1$.

For example, the strings "aba" and "abc" are perfectly balanced but "abb" is not because for the triplet ("bb",'a','b'), the condition is not satisfied.

You are given a string $s$ consisting of lowercase English letters only. Your task is to determine whether $s$ is perfectly balanced or not.

A string $b$ is called a substring of another string $a$ if $b$ can be obtained by deleting some characters (possibly $0$) from the start and some characters (possibly $0$) from the end of $a$.

Input

The first line of input contains a single integer $t$ ($1\le t\le 2\cdot {10}^{4}$) denoting the number of testcases.

Each of the next $t$ lines contain a single string $s$ ($1\le |s|\le 2\cdot {10}^{5}$), consisting of lowercase English letters.

It is guaranteed that the sum of $|s|$ over all testcases does not exceed $2\cdot {10}^{5}$.

Output

For each test case, print "YES" if $s$ is a perfectly balanced string, and "NO" otherwise.

You may print each letter in any case (for example, "YES""Yes""yes""yEs" will all be recognized as positive answer).