Một số nguyên dương n được gọi là số thân thiện nếu gcd(n, s(n)) = 1, trong đó s(n) là số đảo ngược của n.

Yêu cầu: Cho số nguyên dương n. Kiểm tra xem n có phải là số thân thiện hay không, nếu có thì in ra YES, không thì in ra NO.

Input

• Dòng thứ nhất chứa số t (t ≤ 1000) – Thể hiện số lượng testcase.
• t dòng tiếp theo, mỗi dòng chứa số n (1 ≤ n ≤ 1018).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

3
23
45
625

YES
NO
YES

Note

Giải thích: 23 → 23 , s(23) = 32 = 2^5, gcd(23, s(23)) = 1.