#include "iostream"
#include "string.h"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "set"
#include "map"
#include "algorithm"
#include "stdio.h"
#include "math.h"
#define ll long long
#define bug(x) cout<<x<<" "<<"UUUUU"<<endl;
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int N=1e5+100;
///1001
/*
struct Node{
    int a,t1,t2;
    string s;
    bool friend operator< (Node a, Node b){
        if(a.t1==b.t1) return a.t2<b.t2;
        return a.t1<b.t1;
    }
};
Node arr[N];
int main(){
    string s;
    char c;
    map<int,int> M;
    map<int,int> M1;

    int a,t,n,m,t1,t2;
    scanf("%d",&t);
    while(t--){
        M.clear(),M1.clear();
        int k=0,ans=0;
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; ++i){
            cin>>arr[i].a>>arr[i].t1>>c>>arr[i].t2>>arr[i].s;
        }
        sort(arr,arr+m);
        for(int i=0; i<m; ++i){
            a=arr[i].a,t1=arr[i].t1,t2=arr[i].t2,s=arr[i].s;
            if(M[a]==1) continue;
            if(s=="AC"){
                M[a]=1;
                k++;
                ans+=M1[a]*20+t1*60+t2;
            }
            else{
                M1[a]++;
            }
        }
        cout<<k<<" "<<ans<<endl;
    }
    return 0;
}*/

///1002
/*const ll INF=1e17+9;
struct Node{
    ll x,c;
    bool friend operator< (Node a, Node b){
        return a.x<b.x;
    }
};
Node a[3010];
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        ll dp[3050][5],pre[3050]={0,0};
        for(int i=1; i<=n; ++i){
            scanf("%lld%lld",&a[i].x,&a[i].c);
            dp[i][0]=dp[i][1]=INF;
        }
        sort(a+1,a+1+n);
        for(int i=2; i<=n; ++i){
            pre[i]=pre[i-1]+a[i].x-a[1].x;
        }
        dp[1][0]=dp[1][1]=a[1].c;
        for(int i=2; i<=n; ++i){
            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i].c;
            for(int j=1; j<i; ++j){
                ll x=pre[i]-pre[j]-(i-j)*(a[j].x-a[1].x);
                dp[i][0]=min(dp[i][0],dp[j][1]+x);
            }
        }
        cout<<min(dp[n][0],dp[n][1])<<endl;
    }
    return 0;
}*/

///1003
/*
const int N=1e5+100;
int n,t,a[N],b[N];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1; i<=n; ++i){
            scanf("%d",a+i);
            b[i]=a[i];
        }
        int c=a[1];
        for(int i=2; i<=n; ++i){
            c=__gcd(c,a[i]);
        }
        int g=a[1],l=1,r=n;
        for(int i=2; i<=n; ++i){
            if(g==c){
                r=i-1;
                break;
            }
            g=__gcd(g,a[i]);
        }
        g=a[r];
        for(int i=r-1; i>=1; --i){
            if(g==c){
                l=i+1;
                break;
            }
            g=__gcd(g,a[i]);
        }
        //cout<<l<<" "<<r<<endl;
        if(l==1) a[l]=a[l+1];
        else a[l]=a[l-1];
        if(r==1) b[r]=b[r+1];
        else b[r]=b[r-1];
        int ans1=a[1],ans2=b[1];
        for(int i=2; i<=n; ++i){
            ans1=__gcd(ans1,a[i]);
            ans2=__gcd(ans2,b[i]);
        }
        cout<<max(ans1,ans2)<<endl;
    }
    return 0;
}
*/

///1005
/*

const int Mod=1e9+7;
ll PowerMod( ll a, int b, int c ){
    ll ans = 1;
    a %= c;
    while( b ){
        if( b&1 )
            ans = (ans*a)%c;
        b >>= 1;
        a = (a*a)%c;
    }
    return ans;
}
int main(){
    int t,n,k;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        ll ans=0;
        for(int i=1; i<=n; ++i){
            ans+=PowerMod(i,k,Mod);
            ans+=Mod;
            ans%=Mod;
        }
        cout<<(ans+Mod)%Mod<<endl;
    }
    return 0;
}*/

///1008
/*const int Mod=1e9+7;
const int N=3;
struct Mat{
    ll m[N][N];
    Mat(){
        mem(m);
    }
    Mat friend operator* (Mat a, Mat b){
        Mat c;
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
            for(int k=0; k<N; k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;
        return c;
    }
};
Mat PowMod(Mat a, ll b){
    Mat c;
    for(int i=0; i<N; ++i) c.m[i][i]=1;
    while(b){
        if(b&1) c=c*a;
        a=a*a;
        b>>=1;
    }
    return c;
}
int main(){
    int t;
    ll n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        Mat s,a,ans;
        a.m[0][0]=1,a.m[0][1]=1,a.m[0][2]=1;
        s.m[0][2]=1,s.m[1][0]=1,s.m[2][1]=1,s.m[2][2]=1;
        ans=a*PowMod(s,n-2);
        ll ans0=0;
        ans0=ans.m[0][0]+ans.m[0][1]+ans.m[0][2];
        ans0%=Mod;
        cout<<ans0<<endl;
    }
    return 0;
}*/