Self-Replicating Number

Interview

Time limit2sMemory limit128 MB

Summary

Check whether squaring an integer N reproduces N as the trailing digits of N squared.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

A positive integer N is called a self-replicating number if, after squaring N, the final decimal digits of N^2 are exactly N.

For example, 5^2 = 25, and the last digit of 25 is 5, so 5 is a self-replicating number. Also, 76^2 = 5776, and the last two digits of 5776 are 76, so 76 is also a self-replicating number.

Given a positive integer N, write a program that determines whether N is a self-replicating number.

Input

The first line contains the number of test cases T (1 <= T <= 20).

Each of the next T lines contains one positive integer N (1 <= N <= 1000).

Output

For each test case, print YES if the given number is a self-replicating number, and NO otherwise.

Examples1

Example 1
Input
```
4
1
6
76
89
```
Expected output
```
YES
YES
YES
NO
```