K. The Identity Crisis of Abdelaleem: A Prime Substring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Abdelaleem and AbdulMalekZarzur, were engrossed in a peculiar challenge. Abdelaleem had a binary string $$$s$$$, a sequence of zeros and ones, and he dared AbdulMalekZarzur to find a substring within it that represented a binary representation of a prime number.

With furrowed brows, AbdulMalekZarzur accepted the challenge. He scrutinized the string, searching for patterns that would reveal the elusive primes. But try as he might, the binary sequence seemed to be devoid of any such substring.

Frustrated and disheartened, AbdulMalekZarzur sought advice from his wise friend, Yousef, renowned for his mathematical prowess. He beseeched Yousef for guidance, hoping to unravel the mystery of prime substrings.

But Yousef, in a surprising turn of events, declined to assist, urging AbdulMalekZarzur to embark on his own journey of discovery. Determined to prove himself, AbdulMalek Zarzur resolved to tackle the new challenge, armed with determination and mathematical insight.

As the sun dipped below the horizon, casting long shadows over Binaryville, AbdulMalekZarzur delved deeper into the binary labyrinth, his resolve unshaken. For in the realm of numbers, where mysteries abound, every challenge is an opportunity to uncover the hidden truths that shape our world.

Input

The first line contains an integer $$$T$$$ – the number of test cases.

For each test case:

The first line contains the binary string $$$s$$$ ($$$1 \leq |s| \leq 5\times 10^5$$$).

Output

For each test case, output "YES" in a separate line if AbdulMalekZarzur can find any substring that represented a binary representation of a prime number, otherwise output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as positive answers.

Example
Input
3
1
111
101101
Output
No
Yes
Yes
Note

A substring of a binary string is a contiguous sequence of characters (bits) taken from the original binary string. For instance, if the binary string is "1010101", some of its substrings could be "10", "101", "1010", "10101", and so on. Each substring consists of consecutive characters from the original string, maintaining their order.