#include<iostream>
#include<cstdio>
#include<cassert>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int n;
ll query[100010];
//           1  2  3  4  5  6  7  8  9 10 11 12
ll m[]=  {0,31,28,31,30,31,30,31,31,30,31,30,31};
ll m_r[]={0,31,29,31,30,31,30,31,31,30,31,30,31};

struct node{
    int ans_year;
    int ans_month;
    int ans_day;
    bool bc;
}ans[2299239];

bool is_bc=true;
bool glg=false;//geligao lili

bool check_r(int year){
    if(is_bc==true){
        if((year-1)%4==0){
            return true;
        }
    }
    else{
        if(glg==true){
            if( (year%4==0&&year%100!=0) || (year%400==0) )return true;
        }
        else{
            if(year%4==0)return true;   
        }
    }
    return false;
}

bool is_r(ll year){
    if(year<0){
        return (-year-1ll)%4ll==0;
    }
    else if(year<=1582){
        return year%4ll==0;
    }
    else{
        return year%4ll==0&&(year%100ll!=0||year%400ll==0);
    }
    return false;
}

ll past(ll year_nowa,ll year_to){//for glg time
    ll rn=0;if(is_r(year_to))rn--;
    rn+=(year_to/4ll)-(year_to/100ll)+(year_to/400ll);
    rn-=(year_nowa/4ll)-(year_nowa/100ll)+(year_nowa/400ll);
    return (year_to-year_nowa)*365ll+rn;
}

void predo(){
    int day=1,month=1,year=4713;

    int time=0;
    while(time<2299239){
        //check runnian
        bool is_r=check_r(year);

        ans[time].ans_day=day;
        ans[time].ans_month=month;
        ans[time].ans_year=year;
        ans[time].bc=is_bc;
        //checkers
        if(day==4&&month==10&&year==1582&&is_bc==false){
            day=15;
            glg=true;
            time++;
            continue;
        }
        else if(day==31&&month==12&&year==1&&is_bc==true){
            day=1;
            month=1;
            year=1;
            is_bc=false;
            time++;
            continue;
        }
        else if(day==m[month]&&is_r==false){
            if(month==12){
                if(is_bc==true){
                    year--;
                    month=1;
                    day=1;
                    time++;
                    continue;
                }
                else{
                    year++;
                    month=1;
                    day=1;
                    time++;
                    continue;
                }
            }
            else{
                month++;
                day=1;
                time++;
                continue;
            }
        }
        else if(day==m_r[month]&&is_r==true){
            if(month==12){
                if(is_bc==true){
                    year--;
                    month=1;
                    day=1;
                    time++;
                    continue;
                }
                else{
                    year++;
                    month=1;
                    day=1;
                    time++;
                    continue;
                }
            }
            else{
                month++;
                day=1;
                time++;
                continue;
            }
        }
        else day++;
        //final round
        time++;
    }
}

void solve(ll pasx){
    pasx-=2299239ll;

    ll year=1583;

    ll l=1583,r=1e9;
    while(l<r){
        ll mid=(l+r+1)>>1;
        if(past(year,mid)<=pasx){
            l=mid;
        }
        else{
            r=mid-1;
        }
    }
    ll ansy,ansm,ansd;
    ansy=l;
    //cout<<l<<" ";
    pasx-=past(year,l);
    if(is_r(l)){
        for(int i=1;i<=12;i++){
            if(pasx-m_r[i]>=0){
                pasx-=m_r[i];
            }
            else{
                ansm=i;
                break;
            }
        }
    }
    else{
        for(int i=1;i<=12;i++){
            if(pasx-m[i]>=0){
                pasx-=m[i];
            }
            else{
                ansm=i;
                break;
            }
        }
    }
    for(int i=1;i;i++){
        if(pasx)pasx--;
        else{
            ansd=i;
            break;
        }
    }
    cout<<ansd<<" "<<ansm<<" "<<ansy<<endl;
}

int main(){
    //cout<<past(1583,2020);

    ios::sync_with_stdio(false);
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>query[i];
    }

    predo();

    for(int i=1;i<=n;i++){
        ll wt=query[i];
        if(query[i]<2299239ll){
            cout<<ans[wt].ans_day<<" "<<ans[wt].ans_month<<" "<<ans[wt].ans_year;
            if(ans[wt].bc==true){
                cout<<" BC";
            }
            cout<<endl;
        }
        else{
            solve(query[i]);
        } 
    }

    return 0;
}

#include<iostream>
#include<bitset>
#include<stdio.h>
#define ll long long
using namespace std;
int n,m,c,k;
ll animal[1000010];
bitset<70>wei;
bitset<70>ans;
int pos,food;

int main(){
    wei.reset();
    ans.set();
    ios::sync_with_stdio(false);
    //freopen("zoo.in","r",stdin);
    //freopen("zoo.out","w",stdout);
    cin>>n>>m>>c>>k;

    for(int i=1;i<=n;i++){
        cin>>animal[i];
        for(int j=0;j<=k-1;j++){
            if(animal[i]&(1ll<<j)){
                wei[j]=1;
            }
        }
    }
    for(int i=1;i<=m;i++){
        cin>>pos>>food;
        if(wei[pos]==0){
            ans[pos]=0;
        }
    }
    //spj


    unsigned long long final=1;
    bool flag=false;
    bool spj=true;
    for(int i=k-1;i>=0;i--){
        if(ans[i]==1){
            final*=2;
            flag=true;
        }
        else{
            spj=false;
        }
    }

    if(spj==true&&k==64){
        unsigned long long fff=18446744073709551615;
        fff-=n;
        fff++;
        if(n>0)cout<<fff;
        else{
            cout<<"18446744073709551616";
        }
        return 0;
    }

    if(flag==false){
        cout<<"0";
    }
    else{
        final-=n;
        cout<<final;
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<deque>
#include<utility>
#include<functional>
using namespace std;
int T;
int n;
int sn[1000010];
int ch,vl;
int ori;
deque< pair<int,int> >s1,s2;

int solve(){
    int ret;
    s1.clear();//old snake
    s2.clear();//new snake
    for(int i=1;i<=ori;i++){
        s1.push_back(make_pair(sn[i],i));
    }

    bool flag=false;
    while(1){

        if(s1.size()+s2.size()==2){
            ret=1;
            break;
        }

        pair<int,int> strong;
        pair<int,int> weak;

        weak=s1.front();
        s1.pop_front();

        if(s2.empty()||(!s1.empty()&&s1.back()>s2.back())){
            strong=s1.back();
            s1.pop_back();
        }
        else{
            strong=s2.back();
            s2.pop_back();
        }

        pair<int,int> new_snake;
        new_snake.first=strong.first-weak.first;
        new_snake.second=strong.second;

        if(s1.empty()||new_snake<s1.front()){
            //check if it eats?
            ret=s1.size()+s2.size()+2;
            int cnt=0;

            while(true){
                cnt++;
                if(s1.size()+s2.size()+1==2){
                    if(cnt%2==0)ret--;
                    break;
                }

                if(s2.empty()||(!s1.empty()&&s1.back()>s2.back())){
                    strong=s1.back();
                    s1.pop_back();
                }
                else{
                    strong=s2.back();
                    s2.pop_back();
                }

                new_snake.first=strong.first-new_snake.first;
                new_snake.second=strong.second;
                if((s1.empty()||s1.front()>new_snake)&&(s2.empty()||s2.front()>new_snake)){
                    ;
                }
                else{
                    if(cnt%2==0){
                        ret--;
                    }
                    break;
                }
            }
            break;
        }

        else{
            s2.push_front(new_snake);
        }

    }   
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>T;
    for(int i=1;i<=T;i++){
        cin>>n;
        if(i==1){
            ori=n;
            for(int j=1;j<=n;j++){
                cin>>sn[j];
            }
        }
        else{
            for(int j=1;j<=n;j++){
                cin>>ch>>vl;
                sn[ch]=vl;
            }
        }
        cout<<solve()<<endl;
    }
    return 0;
}