Rupsa and Equilateral Triangle (x^2=y^2-z^2)

Rupsa and Equilateral Triangle

Rupsa really loves triangles. One day she came across an equilateral triangle having length of each side as an integer N. She started wondering if it was possible to transform the triangle keeping two sides fixed and alter the third side such that it still remains a triangle, but the altered side will have its length as an even integer, and the line drawn from the opposite vertex to the mid-point of the altered side is of integral length.

Since Rupsa is in a hurry to record a song for Chef as he really loves her songs, you must help her solve the problem as fast as possible.

Input

The first line of input contains an integer T denoting the number of test cases.

Each test-case contains a single integer N.

Output

For each test case, output "YES" if the triangle transformation is possible, otherwise "NO" (quotes for clarity only, do not output).

Constraints

• 1 ≤ T ≤ 10⁶
• 1 ≤ N ≤ 5 x 10⁶

Sub tasks

• Subtask #1: 1 ≤ T ≤ 100, 1 ≤ N ≤ 10⁴ (10 points)
• Subtask #2: 1 ≤ T ≤ 10⁴, 1 ≤ N ≤ 10⁶ (30 points)
• Subtask #3: Original Constraints (60 points)

Example

Input:
2
5
3

Output:
YES
NO

Explanation

• In test case 1, make the length of any one side 6, and it will suffice.

-----------------------------------editorial---------------------------------------------------------------------------------------------------

Pre-requisites

Basic math

Problem

Given an equilateral triangle having length of each side as an integer N. Is it possible to alter one of its' sides such that the height drawn to the altered side has integral length and the altered side has an even integer length?

Explanation

Let's recall the formula for calculating of length of the height of an isosceles triangle. If the length of the height is h, the length of the altered side is b, then h = sqrt(N²-b²/4). Then, h²=N²-b²/4. Let's denote b/2 by c and, since bshould be even, c should be integer. Then, we get h²=N²-c². This is the same as N²=h²+c². According to the statement, h and c should be integer.

Now, the problem is: given an integer N. Find out, whether it is possible to represent N² as a sum of two integer numbers' squares or not.

How to get 10 points

Let's iterate through possible values of h, there are O(N) possible values of h. Then, let's check, if N²-h² is a square of an integer number.

The total complexity of such a solution is O(TN) and it is capable only of solving the first subtask.

How to get 100 points

It is a well known fact that N can be represented as a sum of two perfect squares if and only if N is dividible by a prime of the form (4k+1), where k is an integer number.

So, let's find all the prime numbers not exceeding the maximal value of N. Then, let's pick all the prime numbers that give 1 modulo 4 and for each of them, mark all the numbers that are divisible by them and doesn't exceed the maximal possible value of N (say, MAX_N).

It takes MAX_N/P operations to mark all the integers that are divisible by P. Let's estimate the total number of the operations that we will make.

Since not every number is a prime of the form (4k+1), we can safely assume that the total number of operations won't exceed ∑NP=1NP that won't exceed O(T+MAX_N log MAX_N).

This solution gets 100 points.

---------------------------------------------------code------------------------------------------------------------

1. #include<bits/stdc++.h>
2. using namespace std;
3. typedef long long int lli;
5.  
6. #define test() int test_case;cin>>test_case;while(test_case--)
7. #define fr(i,n) for(int i=0;i<n;i++)
8. #define frr(i,a,n) for(int i=a;i<n;i++)
9. #define sll(a) scanf("%lld",&a)
10. #define sl(a) scanf("%ld",&a)
11. #define si(a) scanf("%i",&a)
12. #define sd(a) scanf("%ld",&a)
13. #define sf(a) scanf("%f",&a)
14. #define rn(a) return a
15. #define pai pair<int,int>
16. #define pal pair<li,li>
17. #define pall pair<lli,lli>
18. #define ff first
19. #define ss second
20. #define mod 1000000007
21. #define mp make_pair
22. #define pb push_back
23. #define pll(a) printf("%lld\n",a)
24. #define pl(a) printf("%lld\n",a)
25. #define pi(a) printf("%d\n",a)
26. #define pd(a) printf("%lf\n",a)
27. #define pf(a) printf("%f\n",a)
28. #define lc (start+end)/2
29. #define rc lc+1
30. int sval;
31. bool pcheck[9000000];
32. bool num[9000000];
34. int main()
35. {
37. pcheck[2]=0;
38. int maxi=6000000;
39. for(int i=2;i<=maxi;i++)
40. {
41. if(!pcheck[i])
42. {
43. bool checker=false;
44. if((i-1)%4==0)
45. {
46. checker=true;
47. num[i]=1;
48. }
49. for(int j=2;i*j<=9000000;j++)
50. {
51. pcheck[i*j]=1;
52. //cout<<i*j<<" ";
53. num[i*j]=checker | num[i*j];
54. }
55. }
56. }
57. test()
58. {
59. int n;
60. scanf("%d",&n);
61. if(n==1)
62. printf("NO\n");
63. else if(num[n])
64. {
65. printf("YES\n");
66. }
67. else
68. printf("NO\n");
69. }
71. return 0;
72. }