// 斜率优化

// 对于dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式

// 为简化描述我们可以只考虑min情况
// 我们对式子中不同的j作差
// 这里姑且用j与k表示
// 不妨设k>j
// 得到差f(k)-f(j)+h(i)*(g(k)-g(j))

// 如果k优于j那么上式<=0
// f(k)-f(j)+h(i)*(g(k)-g(j))<=0
// 如果g函数满足单调，为了方便 我们假设他单调增
// 则【f(k)-f(j)】/【g(k)-g(j)】<=h(i)
// 斜率找到，就是最大且小于h(i)的一组相邻点的斜率，这时的右端点就是dp转移式所要的东西

// 总而言之，当且仅当转移方程满足dp[i]=max/min(f(j)+g(j)*h(i)+H(i))形式且g函数单调
// 我们就可以斜率优化 

// 重在思维与推导，不在板子，此板子仅供参考
#include<bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 5e4;
long long Q[maxn], dp[maxn], s[maxn];

long long f(int j) {
    return dp[j] + (j + s[j]) * (j + s[j]);
}

double Slope(long long j, long long k)   //求斜率
{
    return double(f(k) - f(j)) / (k + s[k] - j - s[j]);
}

int main() {
    ll n, L;
    while (~scanf("%lld%lld", &n, &L)) {
        for (int i = 1; i <= n; i++) {
            int tmp;
            scanf("%d", &tmp);
            s[i] = s[i - 1] + tmp;
        }

        int Left = 1, Right = 1;
        Q[1] = 0;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            while (Left < Right && Slope(Q[Left], Q[Left + 1]) <= 2 * (s[i] + i - L - 1))
                Left++; //维护队首（删除非最优决策）
            int j = Q[Left];
            dp[i] = dp[j] + (i - j - 1 + s[i] - s[j] - L) * (i - j - 1 + s[i] - s[j] - L); //计算当前f
            while (Left < Right && Slope(Q[Right - 1], Q[Right]) >= Slope(Q[Right], i))
                Right--; //维护队尾（维护下凸包性质）
            Q[++Right] = i; //入队
        }
        printf("%lld\n", dp[n]);
    }
    return 0;
}
// solved pzoj 1010

//素数筛与合数分解
//预处理O（sqrt(n)），询问O（sqrt（n））
//调用find_ini() getfac（）
const int maxn=3e6+5;
int prime[maxn],prime_,not_prime[maxn]={1,1};

void prime_ini(){// 素数不可能筛到longlong范围
    for(int i=2; i<maxn; i++){
        if(!not_prime[i])prime[prime_++]=i;//把质数收录
        for(int j=0; 1ll*i*prime[j]<maxn; j++){
            not_prime[i*prime[j]]=1;//对每一个数字枚举他的最小因子
            if(i%prime[j]==0)break;//在往后的话就不是最小因子了
        }
    }
}

int fac[100][2],fac_;
void getfac(int x){ // assert(x>=2)
    fac_=0;//清空fac
    for(int i=0; prime[i]<=x/prime[i]; i++){
        if(x%prime[i]==0){
            fac[fac_][0]=prime[i];
            fac[fac_][1]=0;
            while(x%prime[i]==0){
                fac[fac_][1]++;
                x/=prime[i];
            }
            fac_++;
        }
    }
    if(x!=1){
        fac[fac_][0]=x;
        fac[fac_][1]=1;
        fac_++;
    }
}

//这个板子只能处理正数
//预处理O（n）合数分解O（lgn）
//最大使用范围[1,MAXN),实际使用[1,MAXN);
//调用find_ini() getfac（）
typedef long long ll;
const ll MAXN=1e6+5;
ll prime[MAXN],prime_;
ll min_fac[MAXN]={-9527,1};//0,1
bool not_prime[MAXN]={true,true};//0,1

void prime_ini(){
    for(ll i=2; i<MAXN; i++){
        if(!not_prime[i]){
            prime[prime_++]=i;//把质数收录
            min_fac[i]=i;
        }
        
        for(ll j=0; j<prime_ && i*prime[j]<MAXN; j++){
            not_prime[i*prime[j]]=true;//对每一个数字枚举他的最小因子
            min_fac[i*prime[j]]=prime[j];
            if(i%prime[j]==0)break;//在往后的话就不是最小因子了
        }
    }
}

//当x=0，1会异常，无意义的东西
ll fac[100][2],fac_;
void getfac(int x){
    fac_=0;
    while(x!=1){
        ll little=min_fac[x];
        fac[fac_][0]=little;
        fac[fac_][1]=0;
        while(little!=1 && min_fac[x]==little){
            x/=little;
            fac[fac_][1]++;
        }
        fac_++;
    }
}
//solved poj-1365

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 I;
/*
 * 素数
 * 欧拉定理
 * 费马小定理1 若a为整数，p为质数，则 pow(a,p)%p=a%p
 * 费马小定理2 若a为整数，p为质数，a不是p的倍数 则 pow(a,p-1)%p=1%p=1  （0是2的0倍）
*/
namespace amazing{
    inline ll gcd(ll a,ll b){
        int shift=__builtin_ctzll(a|b);
        b>>=__builtin_ctzll(b);
        while(a){
            a>>=__builtin_ctzll(a);
            if(a<b) swap(a,b);
            a-=b;
        }return b<<shift;
    }
    inline ll mul(ll x,ll y,ll p){// 有误差，要当心使用，wa了可能就是因为他
        ll z=(long double)x/p*y;
        ll res=x*y-z*p;
        return res<p?res+p:res>p?res-p:res;
    }
}

ll qpow(ll a,ll b,ll c){
    ll r=1;
    while(b){
        if(b&1) r=I(r)*a%c;
        a=I(a)*a%c;
        b>>=1;
    }return r;
}
bool miller_rabin(ll n){// O(10*lgn)
    if(n<=1) return false;
    ll t=n-1,k=0;
    while((t&1)==0) t>>=1,k++;
    for(int i=1;i<=10;i++){// 8-10次
        ll a=qpow(rand()%(n-1)+1,t,n);//全部复杂度在这
        for(ll j=1;j<=k;j++){
            ll nex=I(a)*a%n;
            if(nex==1&&a!=1&&a!=n-1) return false;//通不过测试，是合数
            a=nex;
        }
        if(a!=1)return false;//通不过测试，是合数
    }
    return true;// 通过测试可能是伪素数
}
ll pollard_rho(ll n){ // assert(n>1)
    while(true){
        ll c=rand()%(n-1)+1;
        ll x=0,y=0,val=1;
        for(ll i=0;;i++){
            x=amazing::mul(x,x,n)+c;
            if(x>n)x-=n;
//            x=(I(x)*x+c)%n;
            if(x==y) break;
            val=amazing::mul(val,abs(x-y),n);
//            val=I(val)*abs(x-y)%n;// 乘起来是根据 gcd(a,n)|gcd(ab,n)恒成立  且gcd(ab,n)=gcd(ab%n,n)
            if((i&-i)==i||i%127==0){// 太多必然导致val趋于n，太少导致gcd拖慢速度
                ll d=__gcd(val,n);// 乘起来一起算
                if(d==n) break;
                if(d>1) return d;
            }
            if((i&-i)==i) y=x;
        }
    }
}

vector<ll> findfac(ll n){
    vector<ll>res,stk(1,n);
    if(stk.back()==1) return res;
    while(!stk.empty()){
        ll top=stk.back();stk.pop_back();
        if(miller_rabin(top)) res.push_back(top);
        else{// 通不过测试是合数
            ll fac=pollard_rho(top);
            stk.push_back(fac);
            stk.push_back(top/fac);
        }
    }
    return res;
}

ll read(){ll x;scanf("%lld",&x);return x;}

int main(){
    srand(time(NULL));
    for(int T=read();T>=1;T--){
        vector<ll>v=findfac(read());
        sort(v.begin(),v.end());
        if(v.size()==1) printf("Prime\n");
        else printf("%lld\n",v.back());
    }
}

// 最低位的1 ->                  x&-x
// 去掉最低位的1 ->               x&(x-1)
// 有效数字全是1 ->               (x&(x+1))==0
//把最低位的0 变成1->              x|(x+1)
//取出最低位的0并变成1             (~x)&(x+1)
//取出第k位（约定最低位为第0位）     x&(1<<k)


/* all
 
 bit cnt one            ->      cnt_one(x)              ->  int __builtin_popcount (unsigned int x);
 bit rev                ->      rev_dig(x)              ->
 high bit               ->      high_one(x)
 count leading zero     ->      cnt_leading_zero(x)     ->  int __builtin_clz (unsigned int x);
 count trailing zero    ->      cnt_trailing_zero(x)    ->  int __builtin_ctz (unsigned int x);
 get trailing one       ->      get_trailing_one(x)     ->  x&(x^(x+1))
 
 */
typedef unsigned int u32;
namespace bit{
    
    //count the digits of one in binary number
    u32 co[65536u];//bit cnt one
    void cnt_one_ini() {
        for (u32 i = 1; i < 65536u; i++)
            co[i] = co[i >> 1] + (1 & i);
    }
    u32 cnt_one(u32 x) {
        return co[x & 0xffffu] + co[x >> 16];
    }
    
    
    //reverse the digits in binary number
    u32 rd[65536u];//bit rev data
    void rev_digit_ini() {
        for (u32 i = 1; i < 65536u; i++)
            rd[i] = (rd[i >> 1] >> 1) | ((i & 1) << 15);
    }
    u32 rev_dig(u32 x) {
        return rd[x >> 16] | (rd[x & 0xffffu] << 16);
    }
    
    
    //get the highest digit one in binary number
    u32 ho[65536u];//high bit data
    void high_one_ini(){
        ho[1]=1;
        for(u32 i=2;i<65536u;i++){
            ho[i]=ho[i>>1]<<1;// only the one have the highest digit one 1;
        }
    }
    u32 high_one(u32 x){
        return x<65536u ? ho[x]:(ho[x>>16]<<16);
    }
    
    
    //count leading zero
    u32 clz[65536u];//leading zero count
    void cnt_leading_zero_int(){
        clz[0]=16;
        for(u32 i=1;i<65536u;i++){
            clz[i]=clz[i>>1]-1;
        }
    }
    u32 cnt_leading_zero(u32 x){
        if(x<65536u){
            return clz[x]+16;
        }
        else {
            return clz[x>>16];
        }
    }
    
    //count trailing zero
    u32 ctz[65536u];//trailing zero count
    void cnt_trailing_zero_int(){
        ctz[0]=16;
        for(u32 i=1;i<65526u;i++){
            ctz[i]=i&1 ? 0: ctz[i>>1]+1;
        }
    }
    u32 cnt_trailing_zero(u32 x){
        if(x<65536u){
            return ctz[x];
        }
        else {
            return ctz[x&65535u];
        }
    }
    
    //count leading one is more diffcult using count leading zero
    
    
    //提取第k个1
    int kthbit(u32 x, int k) {
        int s[5], ans = 0, t;
        s[0] = x;
        s[1] = x - ((x & 0xAAAAAAAAu) >> 1);
        s[2] = ((s[1] & 0xCCCCCCCCu) >> 2) + (s[1] & 0x33333333u); s[3] = ((s[2] >> 4) + s[2]) & 0x0F0F0F0Fu;
        s[4] = ((s[3] >> 8) + s[3]) & 0x00FF00FFu; t = s[4] & 65535u;
        if (t < k) k -= t, ans |=16, x >>=16;
        t = (s[3] >> ans) & 255u;
        if (t < k) k -= t, ans |= 8, x >>= 8; t = (s[2] >> ans) & 15u;
        if (t < k) k -= t, ans |= 4, x >>= 4; t = (s[1] >> ans) & 3u;
        if (t < k) k -= t, ans |= 2, x >>= 2; t = (s[0] >> ans) & 1u;
        if (t < k) k -= t, ans |= 1, x >>= 1; return ans;
    }
};

//sgf是转移方法
//sgs是前一个状态的集合
int sgf[N],sg[N];
bool sgs[N];
void sgf_ini(){
    sgf[0]=1;
    sgf[1]=1;
    sgf[2]=2;
    for(int i=3;i<20;i++){
        sgf[i]=sgf[i-1]+sgf[i-2];
        //cout<<sgf[i]<<endl;
    }
}
void sg_ini(int n){
    sgf_ini();
    //sg[0]=0;
    for(int i=1;i<=n;i++){
        memset(sgs,0,sizeof(sgs));
        for(int j=1;/**/i-sgf[j]>=0;j++)sgs[sg[i-sgf[j]]]=true;
        for(int j=0;;j++)if(!sgs[j]){
            sg[i]=j;
            break;
        }
    }
    //for(int i=0;i<=n;i++){
    //    printf("%4d %2d",i,sg[i]);
    //    if(i%10==9)cout<<endl;
    //}
}