# Phoenix and Puzzle solution codeforces – Phoenix is playing with a new puzzle, which consists of nn identical puzzle pieces, 2021

## Phoenix and Puzzle solution codeforces

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

Phoenix is playing with a new puzzle, which consists of nn identical puzzle pieces. Each puzzle piece is a right isosceles triangle as shown below. Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

A puzzle piece
Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces
The goal of the puzzle is to create a square using the nn pieces. He is allowed to rotate and move the pieces around, but none of them can overlap and all nn pieces must be used (of course, the square shouldn’t contain any holes as well). Can he do it?

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces
Input Phoenix and Puzzle solution codeforces

The input consists of multiple test cases. The first line contains an integer tt (1t1041≤t≤104) — the number of test cases.

The first line of each test case contains an integer nn (1n1091≤n≤109) — the number of puzzle pieces.

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces
Output Phoenix and Puzzle solution codeforces

For each test case, if Phoenix can create a square with the nn puzzle pieces, print YES. Otherwise, print NO.

Example Phoenix and Puzzle solution codeforces

input

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces
3
2
4
6


output

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces
YES
YES
NO

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces
Note

For n=2n=2, Phoenix can create a square like this:

For n=4n=4, Phoenix can create a square like this:

For n=6n=6, it is impossible for Phoenix to create a square.

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

### Python Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

for s in[*open(0)][1:]:
n=int(s);f=0
while n&1^1:n>>=1;f=1
print('YNEOS'[f*int(n**.5)**2<n::2])

# C++

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

#include <bits/stdc++.h>
using namespace std;

int main()

{

int t;

cin>>t;

while(t--)

{int n;

cin>>n;

int flag=0;

while(n%2==0)

{n/=2;flag=1;}

int val=sqrt(n);

if(val*val==n && flag)

cout<<"YES"<<endl;

else

cout<<"NO"<<endl;}

return 0;}

### FPC

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

var n,t,z:longint;
begin
for t:=t downto 1 do
begin
if (sqrt(n/2)=trunc(sqrt(n/2)))
or (sqrt(n/4)=trunc(sqrt(n/4)))then writeln('YES') else writeln('NO');
end;
end.

### JAVA 11

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

import java.util.*;
import java.io.*;

public class a2oj implements Runnable {

static PrintWriter out;
static int mod = 1000000007;

public static void main(String[] args) {
new Thread(null, new a2oj(), "coderrohan14", 1 << 26).start();
}

@Override
public void run() {
try {
ioSetup();
} catch (IOException e) {
return;
}
}

public static void ioSetup() throws IOException {
if (System.getProperty("ONLINE_JUDGE") == null) {
File f1 = new File("input.txt");
File f2 = new File("output.txt");
out = new PrintWriter(f2);
double prev = System.currentTimeMillis();
solve();
out.println("\n\nExecuted in : " + ((System.currentTimeMillis() - prev) / 1e3) + " sec");
} else {
out = new PrintWriter(System.out);
solve();
}
out.flush();
out.close();
}

static void solve() {
int t = sc.nextInt();
StringBuilder ans = new StringBuilder("");
while (t-- > 0) {
long n = sc.nextLong();
if ((n % 2 == 0 && isPerfectSquare(n / 2)) || (n % 4 == 0 && isPerfectSquare(n / 4))) {
ans.append("YES\n");
} else {
ans.append("NO\n");
}
}
out.println(ans);
}

/****************************************************************************************************************************************************************************************/

static long modInverse(long a, int mod) {
long g = gcd(a, mod);
if (g != 1)
return -1;
else {
return modPower(a, mod - 2L, mod);
}
}

static long modPower(long x, long y, int mod) {
long res = 1;
x = x % mod;
if (x == 0)
return 0;
while (y > 0) {
if ((y & 1) != 0)
res = (res * x) % mod;
y = y >> 1;
x = (x * x) % mod;
}
return res;
}

static int gcd(int a, int b) {
int tmp = 0;
while (b != 0) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}

static long gcd(long a, long b) {
long tmp = 0;
while (b != 0) {
tmp = b;
b = a % b;
a = tmp;
}
return a;
}

static boolean isPrime(long n) {
if (n == 2 || n == 3)
return true;
if (n % 2 == 0)
return false;
for (long i = 3; i * i <= n; i += 2) {
if (n % i == 0)
return false;
}
return n != 1;
}

static boolean isPerfectSquare(long x) {
long sqrt = (long) Math.sqrt(x);
return (sqrt * sqrt) == x;
}

static int digitsCount(long x) {
return (int) Math.floor(Math.log10(x)) + 1;
}

static boolean isPowerTwo(long n) {
return (n & n - 1) == 0;
}

static void sieve(boolean[] prime, int n) { // Sieve Of Eratosthenes
for (int i = 1; i <= n; i++) {
prime[i] = true;
}
for (int i = 2; i * i <= n; i++) {
if (prime[i]) {
for (int j = 2; i * j <= n; j++) {
prime[i * j] = false;
}
}
}
}

static long nCr(long n, long r) { // Combinations
if (n < r)
return 0;
if (r > n - r) { // because nCr(n, r) == nCr(n, n - r)
r = n - r;
}
long ans = 1L;
for (long i = 0; i < r; i++) {
ans *= (n - i);
ans /= (i + 1);
}
return ans;
}

static int floor(int[] a, int v) {
int l = 0, h = a.length - 1;
while (l < h) {
int mid = (l + h) / 2;
if (a[mid] == v)
return mid;
if (v < a[mid])
h = mid;
else {
if (mid + 1 < h && a[mid + 1] < v)
l = mid + 1;
else
return mid;
}
}
return a[l] <= v ? l : -1;
}

static int floor(long[] a, long v) {
int l = 0, h = a.length - 1;
while (l < h) {
int mid = (l + h) / 2;
if (a[mid] == v)
return mid;
if (v < a[mid])
h = mid;
else {
if (mid + 1 < h && a[mid + 1] < v)
l = mid + 1;
else
return mid;
}
}
return a[l] <= v ? l : -1;
}

static int ceil(int[] a, int v) {
int l = 0, h = a.length - 1;
while (l < h) {
int mid = (l + h) / 2;
if (a[mid] == v)
return mid;
if (a[mid] < v)
l = mid + 1;
else
h = mid;
}
return a[h] >= v ? h : -1;
}

static int ceil(long[] a, long v) {
int l = 0, h = a.length - 1;
while (l < h) {
int mid = (l + h) / 2;
if (a[mid] == v)
return mid;
if (a[mid] < v)
l = mid + 1;
else
h = mid;
}
return a[h] >= v ? h : -1;
}

static long catalan(int n) { // n-th Catalan Number
long c = nCr(2 * n, n);
return c / (n + 1);
}

static class Pair implements Comparable<Pair> { // Pair Class
int x;
int y;

public Pair(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof Pair)) {
return false;
}

Pair pair = (Pair) o;

if (x != pair.x) {
return false;
}
if (y != pair.y) {
return false;
}

return true;
}

@Override
public int hashCode() {
long result = x;
result = 31 * result + y;
return (int) result;
}

@Override
public int compareTo(Pair o) {
return (int) (this.x - o.x);
}
}

static class Trip { // Triplet Class
long x;
long y;
long z;

Trip(long x, long y, long z) {
this.x = x;
this.y = y;
this.z = z;
}

@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (!(o instanceof Trip)) {
return false;
}

Trip trip = (Trip) o;

if (x != trip.x) {
return false;
}
if (y != trip.y) {
return false;
}
if (z != trip.z) {
return false;
}
return true;
}

@Override
public int hashCode() {
long result = 62 * x + 31 * y + z;
return (int) result;
}
}

/**************************************************************************************************************************************************************************************/

StringTokenizer st;

}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
return arr;
}

long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextLong();
}
return arr;
}

String nextLine() {
String str = "";
try {
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}

/*
* ASCII Range--->(A-Z)--->[65,90]<<::>>(a-z)--->[97,122]
*/
/******************************************************************************************************************/

static void printArray(int[] arr) {
out.print("[");
for (int i = 0; i < arr.length; i++) {
if (i < arr.length - 1)
out.print(arr[i] + ",");
else
out.print(arr[i]);
}
out.print("]");
out.println();
}

static void printArray(long[] arr) {
out.print("[");
for (int i = 0; i < arr.length; i++) {
if (i < arr.length - 1)
out.print(arr[i] + ",");
else
out.print(arr[i]);
}
out.print("]");
out.println();
}

static void printArray(double[] arr) {
out.print("[");
for (int i = 0; i < arr.length; i++) {
if (i < arr.length - 1)
out.print(arr[i] + ",");
else
out.print(arr[i]);
}
out.print("]");
out.println();
}
/**********************************************************************************************************************/
}



### KOTLIN

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

import java.io.BufferedReader
import java.util.*
import kotlin.math.ceil
import kotlin.math.floor
import kotlin.math.sqrt

// overflow?

val bin = System.in.bufferedReader()

fun main() {
println(if (solve(n)) "YES" else "NO")
}
}

fun solve(n: Int): Boolean = (n % 2 == 0 && isSquare(n/2)) || (n % 4 == 0 && isSquare(n/4))

fun isSquare(n: Int): Boolean {
val sq = sqrt(n.toDouble())
val o1 = floor(sq).toInt()
val o2 = ceil(sq).toInt()
return o1*o1 == n || o2*o2 == n
}

/**
* Implementations:
* - [SimplePrimeChecker]
* - [EratosthenesSieve]
* - [EratosthenesSieveExtended]
* - [Factorizer]
*/
interface PrimeChecker {
fun isPrime(n: Long): Boolean
fun isPrime(n: Int): Boolean = isPrime(n.toLong())

fun primes(): Sequence<Long> = sequence {
var n = 2L
while (true) {
if (isPrime(n)) yield(n)
n++
}
}

fun divisors(n: Long): Set<Long> {
var p = 1L
val res = mutableSetOf<Long>()
while (p*p <= n) {
if (n % p == 0L) {
}
p++
}
return res
}
}

/**
* Implementations:
* - [SimpleFactorizer]
* - [CachedFactorizer]
*/
interface Factorizer {
fun factorize(n: Long): Factorization

fun factorize(n: Int): Factorization =
factorize(n.toLong())
}

class Factorization(factors: Iterable<Long> = emptyList()) {
// TODO: Make immutable Multiset?
val factors = Multiset(factors)

companion object {
fun singleFactor(p: Long): Factorization = Factorization(listOf(p))
}

fun primeFactors(): Iterable<Long> = factors.valuesWithMultiples().map { it.key }
fun factorsAndPowers(): Iterable<Map.Entry<Long, Int>> = factors.valuesWithMultiples()

fun numberOfPrimeFactors(): Int = factors.uniqueValues()

fun numRelativelyPrimeTo(): Long {
var res = number()
for (p in primeFactors()) {
res -= res/p
}
return res
}

fun numberOfDivisors(): Long =
factorsAndPowers().map { it.value + 1L }.product()

fun sumOfDivisors(): Long =
factorsAndPowers().map { (p, pow) ->
var total = 1L
var mult = p
repeat(pow) {
total += mult
mult *= p
}
total
}.product()

fun normalizeForPerfectSquare(): Factorization {
var res = Factorization()
for ((p, q) in factorsAndPowers()) {
if (q % 2 == 1) res *= singleFactor(p)
}
return res
}

fun number() : Long = factorsAndPowers().map { it.key.pow(it.value) }.product()

operator fun times(F: Factorization): Factorization {
val res = Factorization(factors)
return res
}

operator fun div(F: Factorization): Factorization {
val res = Factorization(factors)
res.factors.removeAll(F.factors)
return res
}

operator fun get(factor: Long): Int = factors[factor]

fun isPrime(): Boolean =
factors.size == 1 && factors.iterator().next() == 1L
}

class SimplePrimeChecker: PrimeChecker {
override fun isPrime(n: Long): Boolean {
if (n <= 1L) return false
var i = 2L
while (i * i <= n) {
if (n % i == 0L) return false
i++
}
return true
}
}

val SPC = SimplePrimeChecker()

fun isPrime(n: Int) = SPC.isPrime(n)
fun isPrime(n: Long) = SPC.isPrime(n)

private fun checkInRange(n: Long, max: Long) {
if (n > max) throw Error("Largest supported value is: $max, got:$n")
}

@ExperimentalUnsignedTypes
class EratosthenesSieve(val max: Int): PrimeChecker {
val isPrime = BitArray(max+1, true)

init {
isPrime[0] = false
isPrime[1] = false

for (i in 2..max) {
if (isPrime[i]) {
if (i.toLong() * i <= max) {
for (j in i * i..max step i) {
isPrime[j] = false
}
}
}
}
}

override fun isPrime(n: Long): Boolean {
checkInRange(n, max.toLong())
return isPrime[n.toInt()]
}
}

@ExperimentalUnsignedTypes
class EratosthenesSieveExtended(val max: Long): PrimeChecker {
val sieveSize = sqrt(max.toDouble()).toInt() + 2
val ES = EratosthenesSieve(sieveSize)
val primes: IntArray

init {
val primes = mutableListOf(2)
for (i in 3..sieveSize step 2) {
if (ES.isPrime(i)) {
}
}
this.primes = primes.toIntArray()
}

override fun isPrime(n: Long): Boolean {
if (n <= sieveSize) return ES.isPrime(n.toInt())
checkInRange(n, max)

var i = 0
while (i in primes.indices && primes[i].toLong()*primes[i] <= n) {
if (n % primes[i++] == 0L) return false
}
return true
}

override fun primes(): Sequence<Long> = primes.asSequence().map { it.toLong() }
}

class SimpleFactorizer(val P: PrimeChecker = SimplePrimeChecker()): Factorizer {
override fun factorize(n: Long): Factorization {
val factors = Multiset<Long>()
var i = n
for (d in P.primes()) {
if (d*d > i) break
var c = 0
while (i % d == 0L) {
i /= d
c++
}
if (c > 0) factors.add(d, c)
}
if (i > 1) {
}
return Factorization(factors)
}
}

val SF = SimpleFactorizer(SPC)

fun factorize(n: Int) = SF.factorize(n)
fun factorize(n: Long) = SF.factorize(n)

// https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/
class CachedFactorizer(val max: Int): Factorizer, PrimeChecker {
val divp = IntArray(max+1)

init {
for (i in 1..max) divp[i] = if (i % 2 == 0) 2 else i
var i = 2
while (i * i < max) {
if (divp[i] == i) {
// i is prime
var j = i * i
while (j < max) {
if (divp[j] == j) {
divp[j] = i
}
j += i
}
}
i++
}
}

override fun factorize(n: Long): Factorization {
checkInRange(n, max.toLong())
val factors = Multiset<Long>()
var i = n.toInt()
while (i > 1) {
i /= divp[i]
}
return Factorization(factors)
}

override fun isPrime(n: Long): Boolean {
checkInRange(n, max.toLong())
val ni = n.toInt()
return divp[ni] == ni
}
}

class FactorialFactorization(val max: Int) {
val F = CachedFactorizer(max)
val factorialFactors: Array<Factorization>

init {
val ff = mutableListOf<Factorization>()
for (i in 0..max) {
ff.add(if (i == 0) Factorization() else ff[i-1] * F.factorize(i))
}
factorialFactors = ff.toTypedArray()
}

fun factorial(n: Int): Factorization {
checkInRange(n.toLong(), max.toLong())
return factorialFactors[n]
}

fun ofBionomialCoefficient(n: Int, k: Int): Factorization =
factorial(n) / (factorial(k) * factorial(n-k))
}

// TODO: Include this in general classes?
/**
* Number of different prime factors for all numbers up to [max].
*/
class NumPrimeFactors(val max: Int) {
val numPrimeFactors = IntArray(max+1)

init {
for (v in 2..max) {
if (numPrimeFactors[v] == 0) {
for (j in v..max step v) {
numPrimeFactors[j]++
}
}
}
}

fun numPrimeFactors(n: Int): Int {
checkInRange(n.toLong(), max.toLong())
if (n > max) throw Error("Out of range: $n (max supported:$max)")
return numPrimeFactors[n]
}
}

class Multiset<T>(initial: Iterable<T> = emptyList()): Iterable<T> {
// value -> # of copies
val vs = mutableMapOf<T, Int>()

private var _size = 0
val size: Int
get(): Int = _size

init {
}

fun add(elt: T, copies: Int = 1) {
_size += copies
vs.merge(elt, copies, Int::plus)
}

fun remove(elt: T, copies: Int = 1) {
_size -= copies
val before = vs[elt]
assert(before != null && before >= copies)
val after = before!! - copies
if (after == 0) {
vs.remove(elt)
} else {
vs[elt] = after
}
}

operator fun contains(i: T): Boolean = vs.containsKey(i)

operator fun get(i: T): Int = vs.getOrDefault(i, 0)

fun uniqueValues(): Int = vs.size

fun isEmpty(): Boolean = vs.isEmpty()

override fun iterator(): Iterator<T> = iterator {
for ((v, copies) in vs.entries) {
repeat(copies) { yield(v) }
}
}

fun valuesWithMultiples(): Set<Map.Entry<T, Int>> = vs.entries

for ((v, m) in vs.valuesWithMultiples()) {
}
}

fun removeAll(vs: Multiset<T>) {
for ((v, m) in vs.valuesWithMultiples()) {
remove(v, m)
}
}
}

fun List<Int>.product(): Int = if (isEmpty()) 1 else reduce(Int::times)
fun List<Long>.product(): Long = if (isEmpty()) 1 else reduce(Long::times)

/**
* Faster rewrite of [BitSet].
*/
@ExperimentalUnsignedTypes
class BitArray(val size: Int, init: Boolean = false) {
val vs = UByteArray(((size+1) shr 3) + 1) { if (init) 0xFFu else 0x00u }

operator fun get(i: Int): Boolean = vs[i shr 3] and (1 shl (i and 0x07)).toUByte() != 0.toUByte()

operator fun set(i: Int, v: Boolean) = if (v) set(i) else clear(i)

fun set(i: Int) {
vs[i shr 3] = vs[i shr 3] or (1 shl (i and 0x07)).toUByte()
}

fun clear(i: Int) {
vs[i shr 3] = vs[i shr 3] and (1 shl (i and 0x07)).toUByte().inv()
}
}

// exponentiation in O(log n)
fun Int.pow(n_in: Int): Int {
if (n_in == 0) return 1
var n = n_in
var x = this
var res = 1
while (n > 0) {
if (n % 2 == 1) res *= x
x *= x
n /= 2
}
return res
}

// exponentiation in O(log n)
fun Long.pow(n_in: Int): Long {
if (n_in == 0) return 1L
var n = n_in
var x = this
var res = 1L
while (n > 0L) {
if (n % 2L == 1L) res *= x
x *= x
n /= 2
}
return res
}



### MONO C#

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;

{
static class Program
{
static TextWriter Writer;
private static Queue<string> _currentLineTokens = new Queue<string>();
public static string ReadToken() { while (_currentLineTokens.Count == 0) _currentLineTokens = new Queue<string>(ReadAndSplitLine()); return _currentLineTokens.Dequeue(); }
public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++) matrix[i] = ReadIntArray(); return matrix; }
{
int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++) ret[i][j] = matrix[j][i]; }
return ret;
}
public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++) lines[i] = Reader.ReadLine().Trim(); return lines; }
public static void WriteArray<T>(IEnumerable<T> array) { Writer.WriteLine(string.Join(" ", array)); }
public static void Write(params object[] array) { WriteArray(array); }
public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array) Writer.WriteLine(a); }
private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
public new TValue this[TKey key]
{
get { return ContainsKey(key) ? base[key] : default(TValue); }
set { base[key] = value; }
}
}
private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++) ret[i] = new T(); return ret; }
#endregion=

public static bool NextPermutation(List<int> perm)
{
for (int i = perm.Count - 2; i >= 0; i--)
{
if (perm[i] < perm[i + 1])
{
int min = i + 1;
for (int j = min; j < perm.Count; j++)
if (perm[j] > perm[i] && perm[j] < perm[min])
min = j;

var tmp = perm[i];
perm[i] = perm[min];
perm[min] = tmp;
perm.Reverse(i + 1, perm.Count - i - 1);
return true;
}
}

return false;
}

#region SegmentTree

public static long SegmentTreeFunc(long a, long b)
{
return a + b;
}

public static void Build(long[] a, long v, long tl, long tr)
{
if (tl == tr)
t[v] = a[tl];
else
{
long tm = (tl + tr) / 2;
Build(a, v * 2, tl, tm);
Build(a, v * 2 + 1, tm + 1, tr);
t[v] = SegmentTreeFunc(t[v * 2], t[v * 2 + 1]);
}
}

public static long Query(long v, long tl, long tr, long l, long r)
{
if (l > r)
return 0;
if (l == tl && r == tr)
return t[v];

var tm = (tl + tr) / 2;
var res = SegmentTreeFunc(Query(v * 2, tl, tm, l, Math.Min(r, tm)), Query(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r));
return res;
}

public static long[] t;

#endregion

private static readonly int modulus = 1000000007;
// private static readonly int modulus1 = modulus - 1;

public static long Pow(long a, long b)
{
long y = 1;

while (true)
{
if ((b & 1) != 0)
y = a * y % modulus;
b = b >> 1;
if (b == 0)
return y;
a = a * a % modulus;
}
}

public static long ReversedNumbByPrimeModulo(long a)
{
return Pow(a, modulus - 2);
}

public static long FactByModulo(long a)
{
long ans = 1;

while (a > 0)
{
ans = ans * a % modulus;
a--;
}

return ans;
}

public static long nCkModulo(long n, long k)
{
if (k < n >> 1)
k = n - k;

long ans = 1;
for (long i = n; i > k; i--)
ans = ans * i % modulus;

k = n - k;
var fact = FactByModulo(k);
var revFact = ReversedNumbByPrimeModulo(fact);

ans = ans * revFact % modulus;

return ans;
}

// public static int maxForPrimeCalc = 200000;
// public static List<int> primes = new List<int>(maxForPrimeCalc) {2};
// // public static int[] minPrimeDiv = new int[maxForPrimeCalc + 1];
// public static bool[] isPrime = new bool[maxForPrimeCalc + 1];

// public static void CalcPrimes()
// {
// isPrime[2] = true;
// for (var i = 2; i <= maxForPrimeCalc; i += 2)
// {
// isPrime[i] = false;
// // minPrimeDiv[i] = 2;
// }
// for (var i = 3; i <= maxForPrimeCalc; i += 2)
// {
// isPrime[i] = true;
// }
//
// for (var i = 3; i * i <= maxForPrimeCalc; i += 2)
// {
// if (isPrime[i])
// {
// // minPrimeDiv[i] = i;
// for (var j = i * i; j <= maxForPrimeCalc; j += i)
// {
// if (isPrime[j])
// {
// isPrime[j] = false;
// // minPrimeDiv[j] = i;
// }
// }
// }
// }
// }
//
// public static int[] PrimeDifferentDividersCountHash = new int[maxForPrimeCalc + 1];
//
// private static int PrimeDifferentDividersCount(long numb)
// {
// if (numb == 1)
// return 0;
// if (isPrime[numb])
// return 1;
//
// if (PrimeDifferentDividersCountHash[numb] > 0)
// return PrimeDifferentDividersCountHash[numb];
//
// var divider = minPrimeDiv[numb];
// var prevNumb = numb / divider;
// var ans = PrimeDifferentDividersCount(prevNumb);
//
// if (divider != minPrimeDiv[prevNumb])
// {
// ans += 1;
// }
//
// PrimeDifferentDividersCountHash[numb] = ans;
//
// return ans;
// }

#region Heap

public static void InsertElementInHeap(int value, int[] arr, ref int sizeOfTree)
{
sizeOfTree++;
arr[sizeOfTree] = value;
HeapifyUp(sizeOfTree, arr);
}

public static void HeapifyUp(int cur, int[] arr)
{
while (true)
{
if (cur == 1)
{
return;
}

var parent = cur >> 1;

if (arr[cur] > arr[parent])
{
arr[cur] ^= arr[parent];
arr[parent] ^= arr[cur];
arr[cur] ^= arr[parent];

cur = parent;
continue;
}

break;
}
}

public static int ExtractHeadOfHeap(int[] arr, ref int sizeOfTree)
{
var extractedValue = arr[1];
arr[1] = arr[sizeOfTree];
sizeOfTree--;
HeapifyDown(1, sizeOfTree, arr);
return extractedValue;
}

public static void HeapifyDown(int cur, int sizeOfTree, int[] arr)
{
while (true)
{
var left = cur << 1;
var right = left + 1;
int smallestChild;

if (sizeOfTree < left)
{
return;
}

if (sizeOfTree == left || arr[left] > arr[right])
smallestChild = left;
else
smallestChild = right;

if (arr[cur] < arr[smallestChild])
{
arr[cur] ^= arr[smallestChild];
arr[smallestChild] ^= arr[cur];
arr[cur] ^= arr[smallestChild];

cur = smallestChild;
continue;
}

break;
}
}

#endregion

#region Sorted Set

public class LowerBoundSortedSet<T> : SortedSet<T>
{
private ComparerDecorator<T> _comparerDecorator;
private class ComparerDecorator<T> : IComparer<T>
{
private IComparer<T> _comparer;
public T LowerBound { get; private set; }
public T HigherBound { get; private set; }
private bool _reset = true;
public void Reset()
{
_reset = true;
}
public ComparerDecorator(IComparer<T> comparer)
{
_comparer = comparer;
}
public int Compare(T x, T y)
{
int num = _comparer.Compare(x, y);
if (_reset)
{
LowerBound = y;
}
if (num >= 0)
{
LowerBound = y;
_reset = false;
}
if (num <= 0)
{
HigherBound = y;
_reset = false;
}
return num;
}
}
public LowerBoundSortedSet()
: this(Comparer<T>.Default) {}
public LowerBoundSortedSet(IComparer<T> comparer)
: base(new ComparerDecorator<T>(comparer))
{
_comparerDecorator = (ComparerDecorator<T>) Comparer;
}
public T FindLowerBound(T key)
{
_comparerDecorator.Reset();
this.Contains<T>(key);
return _comparerDecorator.LowerBound;
}
public T FindHigherBound(T key)
{
_comparerDecorator.Reset();
this.Contains<T>(key);
return _comparerDecorator.HigherBound;
}
}

#endregion

static long GCD(long a, long b)
{
while (b > 0) {
a %= b;
a ^= b;
b ^= a;
a ^= b;
}
return a;
}

// private static List<int>[] _divs = new List<int>[100000 + 1];

// private static void CalcDivs()
// {
// for (var i = 0; i < _divs.Length; i++)
// _divs[i] = new List<int>();
//
// for (var i = 1; i < _divs.Length; i++)
// {
// for (var j = i; j < _divs.Length; j += i)
// }
// }

static void Main(string[] args)
{
Writer = new StreamWriter(Console.OpenStandardOutput());

// CalcPrimes();
// CalcDivs();

for (var tmp = 0; tmp < t; tmp++)
{
Solve();
}

Writer.Close();
}

static void Solve()
{

if (n == 1 || n % 2 == 1)
{
Write("NO");
return;
}

n /= 2;
if (CheckSqrt(n))
Write("YES");
else if (n % 2 == 1)
Write("NO");
else if (CheckSqrt(n / 2))
Write("YES");
else
Write("NO");
}

private static bool CheckSqrt(int n)
{
var sqrt = (int) Math.Sqrt(n);
if (sqrt * sqrt < n)
sqrt++;

return sqrt * sqrt == n;
}

public struct MyStruct
{
public int Index;
public int Ans;

public MyStruct(int index, int ans)
{
Index = index;
Ans = ans;
}
}

private static int gcdex (int a, int b, out int x, out int y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
int x1, y1;
int d = gcdex (b%a, a, out x1, out y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}

private static long GetNumb(Dictionary<char, int> letterDic, List<int> permutation, string s)
{
long res = 0;
long mult = 1;
for (var i = s.Length - 1; i >= 0; i--)
{
res += permutation[letterDic[s[i]]] * mult;

mult *= 10;
}

return res;
}

static void Inc(this Dictionary<long, long> dict, long key, long addedValue)
{
if (dict.ContainsKey(key))
else
}

static void Inc(this Dictionary<int, int> dict, int key, int addedValue)
{
if (dict.ContainsKey(key))
else
}
}
}

## Rust

Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces Phoenix and Puzzle solution codeforces

#![warn(
clippy::all,
rust_2018_idioms,
missing_copy_implementations,
missing_debug_implementations,
trivial_casts,
unused_import_braces,
unused_qualifications,
unused_results
)]
#![allow(
clippy::many_single_char_names,
non_snake_case,
unused_imports,
unused_macros,
)]

#[cfg(not(test))]
macro_rules! println {
($($tt:tt)*) => {
let _ = ($($tt)*);
};
}

#[cfg(not(test))]
macro_rules! print {
($($tt:tt)*) => {
let _ = ($($tt)*);
};
}

use crate::io::Io;
use crate::util::*;
use crate::*;
use core::cmp::Ordering::{Equal, Greater, Less};
use core::cmp::{max, min};
use core::iter::{empty, once, repeat, FromIterator};
use core::mem::swap;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, LinkedList, VecDeque};

pub const MODE: Mode = Mode::Multiple;

pub fn solution<B: BufRead + Write>(io: &mut Io<B>) {
//const N_MAX: usize = 100;
//let mut a = [0; N_MAX];
//let a: Vec<(i64, i64)> = io.read_n_pairs(n).collect();
//let a: Vec<(i64, i64, i64)> = io.read_n_triplets(n).collect();
//let a: Vec<i64> = (0..n).map(|_| io.read()).collect();
//println!("{:?}", [false, true].map_bools("1", "0").concat_to_string());

let mut n: u64 = io.read();

if n & 1 == 1 {
io.no();
return;
}

while n & 1 == 0 {
n /= 2;
}

let sq = (n as f64).sqrt() as u64;
if n == sq * sq {
io.yes();
} else {
io.no();
}
}

#[cfg(test)]
fn alternative<B: BufRead + Write>(io: &mut Io<B>) {

let mut a = 1;
while a * a < n {
let a2 = a * a;
if n % a2 == 0 {
let k = n / a2;
if k == k.round_log2_floor() {
io.yes();
return;
}
}
a += 1;
}

io.no()
}

#[cfg(test)]
#[test]
fn test_example() {
let output = |input: &str| output_for(|io| solution(io), MODE, &input);
assert_eq!(
output(
"3
2
4
6"
),
"YES
YES
NO"
.reformat_with_trim(),
);
}

#[cfg(test)]
#[test]
fn test_custom() {
let output = |input: &str| output_for(|io| solution(io), Mode::Single, &input);
assert_eq!(output("1"), "NO\n");
assert_eq!(output("2"), "YES\n");
assert_eq!(output("3"), "NO\n");
assert_eq!(output("4"), "YES\n");
assert_eq!(output("5"), "NO\n");
assert_eq!(output("6"), "NO\n");
assert_eq!(output("7"), "NO\n");
assert_eq!(output("8"), "YES\n");
assert_eq!(output("9"), "NO\n");
assert_eq!(output("10"), "NO\n");
assert_eq!(output("11"), "NO\n");
assert_eq!(output("18"), "YES\n");
for a in 1..100 {
for b in 1..16 {
assert_eq!(output(&format!("{}", a * a * 2i32.pow(b))), "YES\n");
}
}
assert_eq!(output("1000000000"), "NO\n");
}

#[cfg(test)]
#[test]
fn test_matched() {
let matched = |input: &str| {
matched_for(
|io| solution(io),
|io| alternative(io),
Mode::Single,
&input,
)
};

for n in 1..1000 {
let input = format!("{}", n);
matched(&input);
}
}

/*#[cfg(test)]
#[test]
fn test_matched() {
// require each join_to_string
let matched = |input: &str| {
matched_for(
|io| solution(io),
|io| alternative(io),
Mode::Single,
&input,
)
};
for j in 2..=2 {
for args in vec![1..=10; j].each() {
let input = format!("{}", args.join_to_string(" "));
matched(&input);
}
}
}*/
}

pub fn main() {

let mut writer = BufWriter::new(stdout());
let mut io = Io::new(IoPair::new(&mut reader, &mut writer));
solve(solution, MODE, &mut io);
io.flush();
}

use ceil::*;
mod ceil {

use crate::div_euclid::DivEuclid;
use crate::one::One;

#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Ceil<T>(pub T);

impl<T> Div<T> for Ceil<T>
where
T: Add<Output = T> + Clone + DivEuclid + One + Sub<Output = T>,
{
type Output = T;

fn div(self, rhs: T) -> Self::Output {
(self.0 + rhs.clone() - T::one()).div_euclid(rhs)
}
}
}

use into_vec::*;
mod into_vec {
pub trait IntoVec<T> {
fn into_vec(self) -> Vec<T>;
}

impl<I, T> IntoVec<T> for I
where
Self: Sized,
I: IntoIterator<Item = T>,
{
fn into_vec(self) -> Vec<T> {
self.into_iter().collect()
}
}
}

use io::*;
mod io {
use std::fmt::{Debug, Display};

#[derive(Clone, Debug)]
pub struct IoPair<R, W> {
writer: W,
}

#[derive(Clone, Debug)]
pub struct Io<B> {
io: B,
is_writer_bol: bool,
}

impl<R, W> IoPair<R, W> {
pub fn new(reader: R, writer: W) -> Self {
}

pub fn writer_ref(&self) -> &W {
&self.writer
}
}

fn read(&mut self, buf: &mut [u8]) -> io::Result<usize> {
}
}

fn fill_buf(&mut self) -> io::Result<&[u8]> {
}

fn consume(&mut self, amt: usize) {
}
}

impl<R, W: Write> Write for IoPair<R, W> {
fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
self.writer.write(buf)
}

fn flush(&mut self) -> std::io::Result<()> {
self.writer.flush()
}
}

impl<B: BufRead + Write> Io<B> {
pub fn new(io: B) -> Self {
Self {
io,
is_writer_bol: true,
}
}

pub fn get_ref(&self) -> &B {
&self.io
}

pub fn get_mut(&mut self) -> &mut B {
&mut self.io
}

pub fn try_read_str(&mut self) -> Result<&str, io::Error> {
loop {
} else {
let mut end = start + 1;
while end < self.reader_line.len() && !line[end].is_ascii_whitespace() {
end += 1;
}
let word = unsafe { std::str::from_utf8_unchecked(&line[start..end]) };
return Ok(word);
}
}
}

pub fn try_read<T: std::str::FromStr>(&mut self) -> Result<T, io::Error>
where
<T as std::str::FromStr>::Err: Debug,
{
}

pub fn try_read_ascii(&mut self) -> Result<&[u8], io::Error> {
}

pub fn try_read_decimal(&mut self) -> Result<impl '_ + Iterator<Item = u8>, io::Error> {
}

&mut self,
one: u8,
) -> Result<impl '_ + Iterator<Item = bool>, io::Error> {
}

pub fn read_str(&mut self) -> &str {
}

pub fn read<T: std::str::FromStr>(&mut self) -> T
where
<T as std::str::FromStr>::Err: Debug,
{
}

pub fn read_n<T: std::str::FromStr>(&mut self, n: usize) -> impl '_ + Iterator<Item = T>
where
<T as std::str::FromStr>::Err: Debug,
{
}

pub fn read_n_pairs<T1: std::str::FromStr, T2: std::str::FromStr>(
&mut self,
n: usize,
) -> impl '_ + Iterator<Item = (T1, T2)>
where
<T1 as std::str::FromStr>::Err: Debug,
<T2 as std::str::FromStr>::Err: Debug,
{
}

T1: std::str::FromStr,
T2: std::str::FromStr,
T3: std::str::FromStr,
>(
&mut self,
n: usize,
) -> impl '_ + Iterator<Item = (T1, T2, T3)>
where
<T1 as std::str::FromStr>::Err: Debug,
<T2 as std::str::FromStr>::Err: Debug,
<T3 as std::str::FromStr>::Err: Debug,
{
}

pub fn read_ascii(&mut self) -> &[u8] {
}

pub fn read_decimal(&mut self) -> impl '_ + Iterator<Item = u8> {
}

pub fn read_bits(&mut self, one: u8) -> impl '_ + Iterator<Item = bool> {
}

pub fn write<T: Display>(&mut self, value: T) -> &mut Self {
if self.is_writer_bol {
write!(self.io, "{}", value).unwrap();
} else {
write!(self.io, " {}", value).unwrap();
}
self.is_writer_bol = false;
self
}

pub fn writeln<T: Display>(&mut self, value: T) {
if self.is_writer_bol {
writeln!(self.io, "{}", value).unwrap();
} else {
writeln!(self.io, " {}", value).unwrap();
}
self.is_writer_bol = true;
}

pub fn write_all<T: Display, U: IntoIterator<Item = T>>(&mut self, iter: U) -> &mut Self {
for value in iter.into_iter() {
let _ = self.write(value);
}
self
}

pub fn writeln_all<T: Display, U: IntoIterator<Item = T>>(&mut self, iter: U) {
self.write_all(iter).ln();
}

pub fn write_ascii(&mut self, bytes: &[u8]) -> &mut Self {
self.write(std::str::from_utf8(bytes).unwrap())
}

pub fn writeln_ascii(&mut self, bytes: &[u8]) {
self.write_ascii(bytes).ln();
}

pub fn write_join<T: Display>(&mut self, value: T) -> &mut Self {
write!(self.io, "{}", value).unwrap();
self.is_writer_bol = false;
self
}

pub fn ln(&mut self) {
writeln!(self.io).unwrap();
self.is_writer_bol = true;
}

pub fn yes(&mut self) {
self.writeln("YES");
}

pub fn no(&mut self) {
self.writeln("NO");
}

pub fn flush(&mut self) {
let _ = self.io.flush();
}

pub fn writeln_flush<T: Display>(&mut self, value: T) {
self.writeln(value);
self.flush();
}

pub fn writeln_all_flush<T: Display, U: IntoIterator<Item = T>>(&mut self, iter: U) {
self.writeln_all(iter);
self.flush();
}

pub fn ln_flush(&mut self) {
self.ln();
self.flush();
}
}
}

use target::*;
mod target {
#[cfg(test)]
#[test]
fn test_32bit_target() {
use core::mem::size_of;
assert_eq!(size_of::<usize>(), 4, "Codeforces use 32-bit targets");
}
}

use to_iterator::*;
mod to_iterator {
pub trait ToIterator: Clone + IntoIterator {
fn to_iter(&self) -> Self::IntoIter;
}

impl<T> ToIterator for T
where
T: Clone + IntoIterator,
{
fn to_iter(&self) -> Self::IntoIter {
self.clone().into_iter()
}
}
}

use to_vec::*;
mod to_vec {
use crate::to_iterator::ToIterator;

pub trait ToVec<T> {
fn to_vec(&self) -> Vec<T>;
}

impl<I, T> ToVec<T> for I
where
Self: Sized,
I: ToIterator<Item = T>,
{
fn to_vec(&self) -> Vec<T> {
self.to_iter().collect()
}
}
}

use util::*;
mod util {
use std::io::Write;

use crate::io::{Io, IoPair};

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Mode {
Single, // If only the single test case is expected
Multiple, // If multiple test cases are expected
}

pub fn solve<F, B>(func: F, mode: Mode, io: &mut Io<B>)
where
F: Fn(&mut Io<B>),
{
match mode {
Mode::Single => {
func(io);
io.flush();
}
Mode::Multiple => {
for _ in 0..n {
func(io);
io.flush();
}
}
}
}

pub fn output_for<F>(func: F, mode: Mode, input: &str) -> String
where
F: Fn(&mut Io<IoPair<&[u8], Vec<u8>>>),
{
let writer = Vec::new();
let mut io = Io::new(IoPair::new(reader, writer));
solve(func, mode, &mut io);
std::str::from_utf8(io.get_ref().writer_ref())
.unwrap()
.to_string()
}

#[cfg(test)]
pub fn matched_for<F1, F2>(solution: F1, alternative: F2, mode: Mode, input: &str)
where
F1: Fn(&mut Io<IoPair<&[u8], Vec<u8>>>),
F2: Fn(&mut Io<IoPair<&[u8], Vec<u8>>>),
{
assert_eq!(
output_for(|io| solution(io), mode, input),
output_for(|io| alternative(io), mode, input),
"Where left is solution, right is alternative, and input is: {}",
input
);
}

#[cfg(test)]
pub fn join_to_string<T, I>(items: I) -> String
where
T: ToString,
I: IntoIterator<Item = T>,
{
items
.into_iter()
.map(|item| item.to_string())
.collect::<Vec<_>>()
.join(" ")
}

pub trait ReformatWithTrim {
fn reformat_with_trim(self) -> String;
}

impl ReformatWithTrim for &str {
fn reformat_with_trim(self) -> String {
let lines: Vec<String> = self
.trim()
.lines()
.map(|line| line.trim_start().to_string())
.collect();
lines.join("\n") + "\n"
}
}

pub trait FormatBits {
fn pm_fmt(self) -> String;
}

impl FormatBits for &[bool] {
fn pm_fmt(self) -> String {
self.iter()
.map(|item| if *item { "+" } else { "-" })
.collect()
}
}
}

use div_euclid::*;
mod div_euclid {
pub trait DivEuclid {
fn div_euclid(self, rhs: Self) -> Self;
}

macro_rules! impl_ops {
($($type:tt)*) => {
$( impl DivEuclid for$type {
fn div_euclid(self, rhs: Self) -> Self {
self.div_euclid(rhs)
}
}
)*
};
}

impl_ops!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
}

use one::*;
mod one {
pub trait One {
fn one() -> Self;
fn is_one(&self) -> bool;
}

macro_rules! impl_ops {
($($type:tt)*) => {
$( impl One for$type {
fn one() -> Self {
1
}

fn is_one(&self) -> bool {
*self == 1
}
}
)*
};
}

impl_ops!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
}

use log2::*;
mod log2 {
pub trait IntLog2
where
Self: Sized,
{
fn log2_floor(self) -> u32;
fn log2_ceil(self) -> u32;
fn round_log2_floor(self) -> Self;
fn round_log2_ceil(self) -> Self;
}

macro_rules! impl_ops {
($($type:tt)*) => {
$( impl IntLog2 for$type {
fn log2_floor(self) -> u32 {
use core::mem::size_of;
assert!(self > 0);
(size_of::<Self>() * 8) as u32 - self.leading_zeros() - 1
}

fn log2_ceil(self) -> u32 {
assert!(self > 0);
let floor = self.log2_floor();
let round_floor = 1 << floor;
if self == round_floor {
floor
} else {
floor + 1
}
}

fn round_log2_floor(self) -> Self {
1 << self.log2_floor()
}

fn round_log2_ceil(self) -> Self {
1 << self.log2_ceil()
}
}
)*
};
}

impl_ops!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
}