Practice Brute-force and Palindrome with the exercise "Near-Palindromes"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Brute-force
Palindrome

Statement

Goal

A near-palindrome is a word one letter away from being a palindrome, be it by replacement, addition or removal.

Input

Line 1: the number of words N
Next N lines: a word

Output

A single line of zeroes and ones.
For each word in the input, in order, output 1 if the word is a near-palindrome and 0 otherwise.

Constraints

N < 1000
word length < 10000

Words are solely lowercase alphabetic ASCII characters.
This puzzle Really Has Nothing To Do with the Hypersonic challenge.

Example

Input

2
ricecar
racecars

Output

Solve it

A higher resolution is required to access the IDE