Number to Word

# Python code for 8315. Number to Word Problem code: NUMWORD

t="teen"
N="nine"
S="seven"
U={0:'zero' ,1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:S,8:'eight',9:N,10:'ten',11:'eleven',12:'twelve',13:'thir'+t,14:'four'+t,15:'fif'+t,16:'six'+t,17:S+t,18:'eigh'+t,19:N+t,20:'twenty',30:'thirty',40:'forty',50:'fifty',60:'sixty',70:S+'ty',80:'eighty',90:N+'ty',100:'hundred',1000:'thousand'}
def f(m):return U.get(m)
n=input()
b=len(str(n))-1
T=10
if b>3:b=3
k=T**b
if b==0:print f(n),
while n:
    m=n/k
    if k==T:
        m=n/T
        s=n%T
        if s:
            x=f(m*T+s)
            if x:print x,
            else:print f(m*T),f(s),
        else:print f(m*T),  
    if k>T:
        x=f(m)
        y=f(k)
        if x:
            if m:print x,y,
        else:
            x=m/T
            z=m%T
            X=f(x*T)
            if z:print X,f(z),y,
            else:print X,y,      
    n%=k
    if n==0:print
    k/=T

Tiling a Grid With Dominoes

# Python code for 2530. Tiling a Grid With Dominoes Problem code: GNY07H

def tiles(n):
    a = [1,1,5,11,36,95,281]
    if n<7:
        return a[n]
    else:
        i=7
        while i!=n+1:
            k=a[i-1]+5*a[i-2]+a[i-3]-a[i-4]
            a.append(k)
            i+=1
    return a[n]           
h=input
for t in range(h()):
    n =h()
    print t+1, tiles(n)

Househoder Method and Jacobi Rotaion

/* C code to tridiagonalize a Matrix using Householder's Method and then finding the eigen values using Jacobi Rotation Method*/

#include<stdio.h>
#include<math.h>
#define ERROR 0.0000001
//Function to read input matrix
void read_matrix(int order ,float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
        for (j=0;j<order;j++)
            scanf("%f",&matrix[i][j]);
}

//Function to print the matrix
void print_matrix(int order , float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
    {
        for (j=0;j<order;j++)
            printf("%.4f\t",matrix[i][j]);
        printf("\n");
    }
}

int check_symmetric(int n , float a[][n])
{
    int i, j, tag=1;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if (a[i][j]!=a[j][i])
            {
                tag=0;
                break;
            }   
        }
       
        if (tag==0)
            break;
    }

    return tag;
}

//Function to multiply two matrices "a" and "b" and put the result in matrix "c"
float multiply(int n , float a[][n], float b[][n] , float c[][n] )
{
    int i,j,k ;
    float sum;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            sum=0;
            for(k=0;k<n;k++)
                sum=sum+(a[i][k])*(b[k][j]);
            c[i][j]=sum;
        }
}   

/*Function to get an identity matrix*/
void identity(int n , float S[][n])
{
    int i , j;
    for (i=0; i<n;i++)
        for (j=0;j<n;j++)
        {
            if (i==j)
                S[i][i]=1;
            else
                S[i][j]=0;   
        }
}

/*Function to copy one matrix into another matrix*/
void copy(int n, float a[][n] , float b[][n])
{
    int i , j;
    for (i=0;i<n;i++)
        for(j=0;j<n;j++)
            a[i][j]=b[i][j];
}

void transpose_vector(int n, float vector[] , float matrix[][n])
{
    int i,j;
    float sum=0;
   
    for(i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            matrix[i][j] = vector[i]*vector[j];
        }
    }
}

void print_vector(int n, float a[])
{
    int i;
    for (i=0;i<n;i++)
    {
        printf("%12.4f  ",a[i]);
    }
    printf("\n");   
}

void swap(float a[], int i, int j)
{
    float temp;
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

void bubblesort( int n, float a[])
{
    int i , j;
     for(j=n-2;j>=1;j--)
         for(i=0;i<=j;i++)
             if(a[i]>a[i+1])
                 swap(a,i,i+1);        
}

void jacobi_rotation(int n , float a[][n])
{
    int i,j;
    float pi = 3.1415926;
    float S[n][n] , invS[n][n] ,temp1[n][n] ,temp2[n][n], theta;   

    identity(n,S);
    identity(n,invS);

    int u,v,tag=1;
    while(1)
    {
        tag=1;
        for (i=0;i<n;i++)
        {
           
            for (j=i+1 ; j <n;j++)
            {
                if ((a[i][j])!=0)
                {
                    if (a[i][i]!=a[j][j])
                        theta = (atan(2*a[i][j]/(a[i][i]-a[j][j])))/2;

                    else
                    {
                        if (a[i][j]>0)
                            theta = pi/4;
                       
                        else if (a[i][j]<0)
                            theta = -pi/4;
                    }
                                           
                   
                    identity(n,S);
                    identity(n,invS);

                    S[i][i]= invS[i][i]= invS[j][j]=S[j][j]=cos(theta);
                    S[i][j]= invS[j][i]= -sin(theta);
                    S[j][i]= invS[i][j]=  sin(theta);

                    multiply(n,invS,a,temp1);
                    multiply(n,temp1,S,temp2);
   
                    copy(n,a,temp2);
                   
                }
                else continue;
            }   
        }   
   
        for (u=0;u<n;u++)
        {
            for (v=u+1;v<n;v++)
            {
                if (abs(a[u][v]) > ERROR)
                {
                    tag=0;
                    break;
                }   
            }
            if (tag==0)
                break;
        }
   
        if (tag==1)
            break;
   
    }   
}


/*main function*/
int main()
{
    int n,i,j,sign,k;
    scanf("%d",&n);

    float a[n][n] , P[n][n] ,temp1[n][n] ,temp2[n][n] , I[n][n] , w[n], transpose[n][n], x , sum,s,temp;
    read_matrix(n,a);

    int check;
    check = check_symmetric(n,a);
    if (check==0)
    {
        printf("Given matrix is not symmetric\n");
        return 0;
    }
   
    for(i=0;i<n-2;i++)
    {
        j=0;
        sum=0;
        while(j<=i)
        {
            w[j++]=0;
        }
       
        for(k=i+1;k<n;k++)
            sum=sum+a[i][k]*a[i][k];   
       
        s= sqrt(sum);
        if (s==0)
            continue;
        //printf("s : %f\n",s);
        if (j==i+1)
        {
            if (a[i][j]<0)
                sign=-1;
            else
                sign=1;
               
            temp = (1+a[i][j]*sign/s)/2;
            x=sqrt(temp);
            w[j]=x;
            j++;
        }
       
        for (j=i+2;j<n;j++)
        {
            w[j]=(a[i][j]*sign)/(2*s*x);
        }
       
        identity(n, I);
        transpose_vector(n,w,transpose);
       
        for(k=0;k<n;k++)
        {
            for(j=0;j<n;j++)
            {
                P[k][j]=I[k][j]-2*transpose[k][j];
            }
        }

        //print_matrix(n, P);

        multiply(n,a,P,temp1);
       
        multiply(n,P,temp1,temp2);       
        copy(n,a,temp2);
       
        //print_matrix(n, a);
    }
   
    //printf("\nTridiagonal matrix using Householder Method is : \n\n");
    //printf("\n");
    print_matrix(n,a);
   
    //printf("\nEigne values of Tridiagonal  : \n\n");
    jacobi_rotation(n, a);

    float eigen[n];
    for (i=0;i<n;i++)
        eigen[i]=a[i][i];
       
    bubblesort(n,eigen);   
    //printf("\n");
    for (i=n-1;i>=0;i--)
        printf("%.4f\n",eigen[i]);
   
    return 0;   
}

Circular Track

// C code for 9199. Circular Track Problem code: SPEED

#include<stdio.h>
int gcd(int a, int b)
{
    int r ;
        while (b!=0)
        {
            r=a%b;
            a=b;
            b=r;
        }
        return a;
}

int main()
{
    int t,m,n,ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        ans=m>n?m-n:n-m;
        m*=(m<0?-1:1);
        n*=(n<0?-1:1);
        printf("%d\n",ans/(gcd(m,n)));
    }
    return 0;
}

Size Contest

#Python code for 378. Size Contest Problem code: SIZECON
c=0
i=input
exec'b=i();c+=b*(b>0);'*i()
print c

Tanks

// C code for  13675. Tanks Problem code: NEWTANK

#include<stdio.h>
int main()
{
    int test,v,t,i;
    scanf("%d",&test);
    for(i=1;i<=test;i++)
    {
        scanf("%d%d",&v,    &t);
        printf("Case #%d: %d\n",i,v*t);
    }
    return 0;
}

H Number

// C code for 13662. H Number Problem code: HNUM

#include<stdio.h>
int main()
{
    int test, n,i;
    scanf("%d",&test);
   
    for(i=1;i<=test;i++)
    {
        scanf("%d",&n);
        if (n%30==0)
            printf("Case #%d: H-Number\n",i);
        else
            printf("Case #%d: Not H-Number\n",i);   
    }
    return 0;
}

Azooz

// C code for 13677. Azooz Problem code: AZOOZ

#include<stdio.h>
int main()
{
    int t,n,i,j,k;
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        k=1;
        scanf("%d",&n);
        k=3*(n*(n+1)/2);
       
        printf("Case #%d: %d\n",i,k);   
    }
    return 0;
}

Word To Number

#Python code for  7225. Word To Number Problem code: WORDNUM


import re
c="teen";s="seven";e="eigh";n="nine";f="four";X="six";T="thir";y="ty"
U ={'zero':0,'one':1,'two':2,'three':3,f:4,'five':5,X:6,s:7,e+'t':8,n:9,'ten':10,'eleven':11,'twelve':12,T+c:13,f+c:14,'fif'+c:15,X+c:16,s+c:17,e+c:18,n+c:19,'twen'+y:20,T+y:30,'for'+y:40,'fif'+y:50,X+y:60,s+y:70,e+y:80,n+y:90}
M={'thousand':1000,'hundred':100}
def x(s):
 a=re.split(r"[\s-]+",s)
 n=g=0
 for w in a:
  x=U.get(w)
  if x:
   g+=x
  x=M.get(w)
  if x:n+=g*x;g=0
 print n+g
for t in range(input()):x(raw_input())

Egypt

// C code for 9754. Egypt Problem code: SCPC11D

#include<stdio.h>
int main()
{
    int a,b,c;
   
    scanf("%d%d%d",&a,&b,&c);
    while(a&&b&&c)
    {
        if (a>b&&a>c&&b*b+c*c==a*a)
            printf("right\n");
       
        else if (b>c && b>a && c*c+a*a==b*b)   
            printf("right\n");
       
        else if (a*a+b*b==c*c)
            printf("right\n");
        else
            printf("wrong\n");       
   
        scanf("%d%d%d",&a,&b,&c);       
    }
    return 0;
}

Pizza

#Python code for  7169. Pizza Problem code: EGYPIZZA

import math
m=0
n=0
k=0
test=input()
i=0

while i!=test:
    a=raw_input()

    if len(a)!=0:
        if a=="3/4":
            m=m+1
        if a=="1/2":
            n=n+1       
        if a=="1/4":
            k=k+1
        i=i+1           
if m>=k:
    ans=math.ceil(m+n/2.0)

elif m<k:
    k=k-m
    if n%2==0:
        ans = math.ceil(m+n/2.0+k/4.0)
           
    else:
        k=k-2
        ans= math.ceil(m + n/2.0 + k/4.0)

print  int(ans+1)       

GCD (very large numbers)

#Python code to find GCD of two very large numbers

for i in range(input()):
    a,b = [long(i) for i in raw_input().split()]
    while b :
        a,b = b,long(a%b)
    print a

Binary GCD

#Python code to find GCD of two numbers using Binary GCD algorithm

def gcd (a,b):
    if a==0:
        return b
    if b==0:
        return a
   
    shift=0
   
    while (a|b)&1 ==0:
        a>>=1
        b>>=1
        shift+=1
   
    while a&1==0:
        a>>=1
           
    while b:
        while b&1==0:
            b>>=1
        if a>b:
            t=a
            a=b
            b=t
       
        b=b-a
       
    return a<<shift               
   

for i in range(input()):
    a,b=raw_input().split()
    n=int(a)
    m=int(b)
   
    print gcd(n,m)   

GCD2

// C code for  2906. GCD2 Problem code: GCD2

#include <stdio.h>

 int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}

int mod(char s[],int d)
{
    int r = 0,i;

    for(i=0;s[i];i++)
    {
        r=10*r +(s[i] - 48);
        r %= d;
    }
    return r;
}

int main()
{
    int test , a;
    char b[254];

    scanf("%d",&test);

    while(test--)
    {
        scanf("%d%s",&a,b);
   
        if(!a)
            printf("%s\n",b);
       
        else
            printf("%d\n",gcd(a,mod(b,a)));
    }
    return 0;
}

Euler Totient Function

//C code for 4141. Euler Totient Function Problem code: ETF

#include<stdio.h>
int totient(int n)
{
    int i, ans = n;
   
    for (i=2;i*i<=n;i++)
    {
        if (n%i==0)
            ans-=ans/i;
           
        while(n%i==0)
            n/=i;
    }   
   
    if (n!=1)
        ans-=ans/n;
    return ans;   
}       
   
int main()
{
    int test ,n;
   
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d",&n);
        printf("%d\n",totient(n));
   
    }
    return 0;
}

Cards

// C code for  10509. Cards Problem code: CRDS

#include<stdio.h>
int main()
{
    int t;
    long long n;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%lld",&n);
        printf("%lld\n",(n*(3*n+1)/2)%1000007);   
    }
    return 0;
}

Recaman’s Sequence

// C code for 3934. Recaman’s Sequence Problem code: MRECAMAN

#include <stdio.h>
#define max 500000

int tag[10*max+1] ,a[2*max+1];
int main()
{
    int i, n, m;
    for(i=1; i<=max; i++)
    {
        m = a[i-1];
        a[i]= m > i && !tag[m-i]?m - i:m + i;
        tag[a[i]] = 1;
    }
    while(scanf("%d", &n)==1 && n!=-1)
        printf("%d\n", a[n]);
           
        return 0;
}

A Game with Numbers

// C code for 1419. A Game with Numbers Problem code: NGM

#include<stdio.h>
int main()
{
    int n;
    while (scanf("%d",&n)==1)
        (n%10)?(printf("1\n%d\n",n%10)):(printf("2\n"));
    return 0;
}

Binary Stirling Numbers

//C code for 106. Binary Stirling Numbers Problem code: BINSTIRL

#include <stdio.h>
int main()
{
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        printf("%d\n", !((n-m)&((m-1)/2)));
    }
    return 0;
}

Armstrong number

#Python code to print the armstrong numbers in a given range
def armstrong(n):
    m=n
    digits=0
    while m>0:
        digits+=1
        m/=10
    m=n
    N=0
    while m>0:
        N+=pow(m%10,digits)
        m/=10
    if n==N:
        return 1
    else:
        return 0
               
for num in range(1000):
    if armstrong(num+1)==1:
        print num+1                           

Ambiguous Permutations

 //C code for 379. Ambiguous Permutations Problem code: PERMUT2

#include<stdio.h>
int main()
{
    int a[100002],b[100002],n,tag,i,x;
    while(1)
    {
        tag=1;
        scanf("%d",&n);
   
        if (n==0)
            break;
   
        for (i=1;i<=n;i++)
        {
            scanf("%d",&x);
            a[i]=x;
            b[a[i]]=i;
        }   

        for (i=1;i<=n;i++)
            if (a[i]!=b[i])
            {
                tag=0;
                break;
            }
        if (tag==0)
            printf("not ambiguous\n");
        else   
            printf("ambiguous\n");
    }   
    return 0;
}

Street Parade

#Python code for  95. Street Parade Problem code: STPAR

import re
while 1:
    a=[]
    s=[]
    b=input()
    if b==0:
        break
    else:
        p=1
        for x in re.sub("[^\w]"," ",raw_input()).split():
            a.append(int(x))       
       
        s.append(a[0])
       
        for i in range(1 , b ):
            k=len(s)
            while a[i]>s[k-1] and s[k-1]==p:
                s.pop()
                p+=1
                k=len(s)
                if k==0:
                    break
            s.append(a[i])
       
        k=len(s)   
        while s[k-1]==p:
            s.pop()
            p+=1
            k=len(s)
            if k==0:
                break
   
        if len(s)==0:
            print "yes"
        else:
            print "no"                    

Sieve of Eratosthenes

#Python code to find all primes in given range using Sieve of Eratosthenes algo.

def Sieve_of_Eratosthenes(n):
    composites=[]
    primes=[]
    for a in range(2, n+1):
        if a not in composites:
            primes.append(a)
        for b in range(a*a, n+1,a):
            composites.append(b)
    return primes       
print Sieve_of_Eratosthenes(1000)

28 digits of phi (Golden ratio)

#Python code to computer first 28 digits of golder ration (phi)

from decimal import*
def babylonian(m):
    n=m
    xn=2
    yn=3
    error=Decimal(10**(-323))
    #print error
    while abs(yn-xn)>error:
        xn=Decimal(yn)
        yn=Decimal((xn+n/xn)/2)
    return Decimal(yn)
print (1+babylonian(5))/2       

To read more on Golden ratio......     

27 digits of e (Euler's number)

from decimal import Decimal
def fact(n): 
    if n == 0: 
        return 1 
        else: 
            return n*fact(n-1) 

def euler():
    i=0
    total=0
    n=0
    while i!=170:
        k=fact(n)
        total=Decimal(total+10**100/k)
       
        n+=1
        i=i+1
    return total    /10**100
       
ans=Decimal(euler())
print ans

To read more on Euler's number....

Lucas number

def Lucas(n):
    a=[]
    i=0
    while i!=n+1:
        if i==0:
            a.append(2)
        elif i==1:
            a.append(1)
        else:
            a.append(a[i-1]+a[i-2])
        i+=1   
    return a[n]       

print Lucas(input())


Read more about Lucas Number..           

1 Lac Digits of Pi

def arccot(x, dig):
    powx=total=10**(11+dig)/x
    n=3
    sign=term=-1
    while term:
        powx /= x*x
        term=powx / n
        total+=sign*term
        n+=2
        sign=-sign
    return total/pow(10,10)
   
def pi(dig):
    pi=4 * (4*arccot(5, dig) - arccot(239, dig)) #Machin's Formula
    return pi/10

print pi(100000)       

Cube Root Truncation

291. Cube Root Problem code: CUBERT

def lower_bound(high,low, n):
    while low<=high:
        mid= (low+high)/2
        a= mid*mid*mid
        b=(mid+1)*(mid+1)*(mid+1)
   
        if a==n or (a<n and b>n):
            return mid
        elif a<n:
            low=mid+1
        else:
            high=mid-1
    return mid
i=0
t=input()
while i<t:
     s1=raw_input()
     if(len(s1)>0):
           i+=1  
           n=long(s1)
           ans1=long(pow(n,1/3.0))
          
           k=long(pow(n,1/2.0)*pow(10,10))
           n*=pow(10,30)
        
           ans=lower_bound(k,long(ans1 *pow(10,10)),n)
           ans=str(ans)
           root=ans[:-10]+"."+ans[-10:]
           count=0
           for c in root:
                  if(c>='0' and c<='9'):
                        count=(count%10+int(c))%10
           final=str(count)+" "+root
           print(final)

Heptadecimal Numbers

7108. Heptadecimal Numbers Problem code: HEPNUM
while 1:
    a,b=raw_input().split()
    if a=='*' and b=='*':break
    m=len(a)
    n=len(b)
    if m<n:a=(n-m)* '0'+a
    elif n<m:b= (m-n)*'0'+b           
    if a>b:print ">"
    elif a==b:print "="
    else:print "<"            

Last Non-Zero Digit of Factorials

2124. Last Non-Zero Digit of Factorials Problem code: FCTRL4

def P(k):
    A=[6,2,4,8]
    if k<1:
        return 1
    else:
        return A[k%4]

def L(N):
    A=[1,1,2,6,4]
    if N<5:
        return A[N]
    else:
        return (P(N/5)*L(N/5)*L(N%5))%10

while True:
    try:
        a= raw_input()
        print L(int(a))       
    except EOFError:
        break

Tridiagonalization using Given's Method

#include<stdio.h>
#define max 1000
#include<math.h>

//Function to read input matrix
void read_matrix(int order ,float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
        for (j=0;j<order;j++)
            scanf("%f",&matrix[i][j]);
}

//Function to print the matrix
void print_matrix(int order , float matrix[][order])
{
    int i, j;
    for (i=0; i<order;i++)
    {
        for (j=0;j<order;j++)
            printf("%f\t",matrix[i][j]);
        printf("\n");
    }
}

//Function to multiply two matrices "a" and "b" and put the result in matrix "c"
float multiply(int n , float a[][n], float b[][n] , float c[][n] )
{
    int i,j,k ;
    float sum;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            sum=0;
            for(k=0;k<n;k++)
                sum=sum+(a[i][k])*(b[k][j]);
            c[i][j]=sum;
        }
}   

/*Function to get an identity matrix*/
void identity(int n , float S[][n])
{
    int i , j;
    for (i=0; i<n;i++)
        for (j=0;j<n;j++)
        {
            if (i==j)
                S[i][i]=1;
            else
                S[i][j]=0;   
        }
}

/*Function to copy one matrix into another matrix*/
void copy(int n, float a[][n] , float b[][n])
{
    int i , j;
    for (i=0;i<n;i++)
        for(j=0;j<n;j++)
            a[i][j]=b[i][j];
}

/*main function*/
int main()
{
    int n,i,j;

    printf("Enter the order of matrix : ");
    scanf("%d",&n);
    float a[n][n] , S[n][n] , invS[n][n] ,temp1[n][n] ,temp2[n][n];   
    read_matrix(n,a);

    identity(n,S);
    identity(n,invS);

    for (i=0;i<=n-3;i++)
    {
        for (j=i+2 ; j <= n-1;j++)
        {
            if ((a[i][j])!=0)
            {
                float theta = atan(a[i][j]/a[i][i+1]);

                identity(n,S);
                identity(n,invS);

                S[i+1][i+1]= invS[i+1][i+1]= invS[j][j]=S[j][j]=cos(theta);
                S[i+1][j]= invS[j][i+1]= -sin(theta);
                S[j][i+1]= invS[i+1][j]=  sin(theta);

                multiply(n,invS,a,temp1);
                multiply(n,temp1,S,temp2);
   
                copy(n,a,temp2);
            }
            else continue;
        }   
    }   
    print_matrix(n,a);
    return 0;   
}

8057. Square Free Factorization Problem code: AMR10C

# Square-Free Factorization

prime=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997 ,1009 ,1013]
def free_square_factors(n):
    root = pow(n,0.5)
    ret=0
    i=0
    while prime[i]<=root:
        if n%prime[i]==0:
            count=0
            while n%prime[i]==0:
                count +=1
                n/=prime[i]
            root=pow(n,0.5)
            if count>ret:   
                ret= count
        i+=1
    if n>1 and ret<1:
        ret = 1
    return ret
for t in range(input()):
    n=input()
    print free_square_factors(n)