////
/////*#include<cstdio>
////#include<cstring>
////#include<algorithm>
////using namespace std;
////struct cc
////{
////    char s[111];
////} a[222];
////int main()
////{
////    int n;
////    while(~scanf("%d",&n))
////    {
////        int fu1=0,fu2=0,k=0;
////        scanf("%s",a[0].s);
////        if(a[0].s[0]=='-')
////            fu1=1;
////        for(int i=1;i<n; i++)
////        {
////            fu2=0;
////            scanf("%s",a[i].s);
////            if(a[i].s[0]=='-')
////            {
////                fu2=1;
////            }
////            if(fu1==1&&fu2==0)
////            {
////                k=i;
////                fu1=0;
////            }
////            else if(fu1==1&&fu2==1)
////            {
////                int l1=0,l2=0;
////                for(int j=1; a[k].s[j]!='\0'; j++)
////                {
////                    if(a[k].s[j]!='0')
////                    {
////                        l1=j;
////                        break;
////                    }
////                }
////                int len1=strlen(a[k].s)-l1;
////                for(int j=1; a[i].s[j]!='\0'; j++)
////                {
////                    if(a[i].s[j]!='0')
////                    {
////                        l2=j;
////                        break;
////                    }
////                }
////                int len2=strlen(a[i].s)-l2;
////                if(len2<len1)
////                {
////                    k=i;
////                }
////                else if(len2==len1)
////                {
////                    for(int j=l1,l=l2; a[k].s[j]!='\0';)
////                    {
////                        if(a[k].s[j]>a[i].s[l])
////                        {
////                            k=i;
////                            break;
////                        }
////                        else if(a[k].s[j]==a[i].s[l])
////                        {
////                            j++;
////                            l++;
////                        }
////                        else
////                        {
////                            break;
////                        }
////                    }
////                }
////            }
////            else if(fu1==0&&fu2==0)
////            {
////                int l1=0,l2=0;
////                for(int j=0; a[k].s[j]!='\0'; j++)
////                {
////                    if(a[k].s[j]!='0')
////                    {
////                        l1=j;
////                        break;
////                    }
////                }
////                int len1=strlen(a[k].s)-l1;
////                for(int j=0; a[i].s[j]!='\0'; j++)
////                {
////                    if(a[i].s[j]!='0')
////                    {
////                        l2=j;
////                        break;
////                    }
////                }
////
////                int len2=strlen(a[i].s)-l2;
////                if(len2>len1)
////                {
////                    k=i;
////                }
////                else if(len2==len1)
////                {
////                    for(int j=l1,l=l2; a[k].s[j]!='\0';)
////                    {
////                        if(a[k].s[j]<a[i].s[l])
////                        {
////                            k=i;
////                            break;
////                        }
////                        else if(a[k].s[j]==a[i].s[l])
////                        {
////                            j++;
////                            l++;
////                        }
////                        else
////                        {
////                            break;
////                        }
////                    }
////                }
////            }
////        }
////        int ll;
////        if(a[k].s[0]=='-')
////        {
////            printf("-");
////            for(int i=1; a[k].s[i]!='\0'; i++)
////            {
////                if(a[k].s[i]!='0')
////                {
////                    ll=i;
////                    break;
////                }
////            }
////            for(int i=ll; a[k].s[i]!='\0'; i++)
////                printf("%c",a[k].s[i]);
////            printf("\n");
////        }
////        else
////        {
////            for(int i=0; a[k].s[i]!='\0'; i++)
////            {
////               // printf("%c  !\n",a[k].s[i]);
////                if(a[k].s[i]!='0')
////                {
////                    ll=i;
////                    break;
////                }
////            }
////            for(int i=ll; a[k].s[i]!='\0'; i++)
////                printf("%c",a[k].s[i]);
////            printf("\n");
////        }
////    }
////}
////#include<cstdio>
////#include<algorithm>
////using namespace std;
////int main()
////{
////    int n;
////    while(~scanf("%d",&n))
////    {
////        int a[1010];
////        int  sum,ss,pos=0,mms=1e9,ms=-1e9;
////        for(int i=0; i<n; i++)
////            scanf("%lld",&a[i]);
////        b1=e1=p1=0;
////        b2=e2=p2=0;
////        sum=ss=a[0];
////        for(int i=1; i<n; i++)
////        {
////            sum+=a[i];
////            if(sum>a[i])
////            {
////                sum=a[i];
////            }
////            /*if(ss<0)
////            {
////               ss=a;
////            }
////            else ss+=a;
////            ms=max(ms,ss);
////if(sss>0)
////{
////    sss=a;
////}
////else sss+=a;
////mms=min(mms,sss);//&#65533;&#65533;С&#65533;&#65533;&#65533;&#65533;&#65533;&#65533;
////s+=a;
////
////}
////printf("%lld\n",max(ms,s-mms));
////}
////}
////#include<stdio.h>
////#include<string.h>
////int main()
////{
////    char str[30],s1[20];
////    int i,j,len,s,sum1,sum2,flag;
////    while(gets(str)!=NULL)
////    {
////        len=strlen(str);
////        sum1=sum2=0;
////        flag=0;
////        for(i=0,j=0;i<len;i++)
////        {
////            if(str[i]>='a'&&str[i]<='z')
////                s1[j++]=str[i];
////            else if(str[i]==' '&&str[i-1]!='+')
////            {
////                s1[j]='\0';
////                if(!strcmp(s1,"zero")) s=0;
////                else if(!strcmp(s1,"one")) s=1;
////                else if(!strcmp(s1,"two")) s=2;
////                else if(!strcmp(s1,"three")) s=3;
////                else if(!strcmp(s1,"four")) s=4;
////                else if(!strcmp(s1,"five")) s=5;
////                else if(!strcmp(s1,"six")) s=6;
////                else if(!strcmp(s1,"seven")) s=7;
////                else if(!strcmp(s1,"eight")) s=8;
////                else if(!strcmp(s1,"nine")) s=9;
////                j=0;
////                if(!flag)
////                    sum1=sum1*10+s;
////                else
////                    sum2=sum2*10+s;
////            }
////            else if(str[i]=='+')
////                flag=1;
////        }
////        if(sum1==0&&sum2==0)
////            break;
////        else
////            printf("%d\n",sum1+sum2);
////    }
////    return 0;
////}
////#include<stdio.h>
////#include<string>
////#include<iostream>
////#include<map>
////using namespace std;
////const int MAXN=1000;
////int main()
////{
////    map<string,int>color;
////    string cnt;
////    string index;
////    int i;
////    int n;
////    int max;
////    while(scanf("%d",&n),n)
////    {
////        max=0;
////        for(i=0; i<n; i++)
////        {
////            cin>>cnt;
////            color[cnt]++;
////            if(color[cnt]>max)
////            {
////                index=cnt;
////                max=color[cnt];
////            }
////
////        }
////        cout<<index<<endl;
////    }
////    return 0;
////}
////#include<cstdio>
////#include<string>
////#include<cstring>
////#include<map>
////#include<iostream>
////using namespace std;
////const int MAX=3000+5;
////int main()
////{
////    map<string,string>zidian;
////    map<string,int>biaoji;
////    string x;
////    string y;
////    string begin;
////    string end;
////    cin>>begin;
////    int i,n;
////    int max;
////    while(cin>>x&&x!="END")
////    {
////        cin>>y;
////        zidian[y]=x;
////        biaoji[y]=1;
//////        cout<<zidian[y]<<endl;
////    }
////    cin>>begin;
////    getchar();
////    char s[MAX];
////    while(1)
////    {
////        gets(s);
////        if(strcmp(s,"END")==0)
////        {
////            break;
////        }
////        int len=strlen(s);
////        y="";
////        for(int i=0;i<len;i++)
////        {
////            if(s[i]<'a'||s[i]>'z')
////            {
////                if(zidian[y]!="")
////                {
////                    cout<<zidian[y];
////                }
////                else
////                {
////                    cout<<y;
////                }
////                y="";
////                cout<<s[i];
////            }
////            else
////            {
////                y+=s[i];
////            }
////        }
////       cout<<endl;
////    }
////}
////#include <iostream>
////#include <algorithm>
////#include <map>
////#include <cstdio>
////#include <string>
////#include <string.h>
////using namespace std;
////int main()
////{
////  string a,b;
////  map<string,string> mp;
////  cin>>a;
////  while(cin>>a&&a!="END")
////  {
////    cin>>b;
////    mp[b]=a;
////  }
////  cin>>a;
////  getchar();
////  char ch[3005];
////  while(1)
////  {
////      gets(ch);
////      int i,len;
////    if(strcmp(ch,"END")==0)
////        break;
////    len=strlen(ch);
////    b="";
////    for(i=0;i<len;++i)
////    {
////        if(ch[i]<'a'||ch[i]>'z')
////        {
////           if(mp[b]!="")
////             cout<<mp[b];
////           else
////             cout<<b;
////            b="";
////           cout<<ch[i];
////        }
////        else
////            b+=ch[i];
////    }
////    cout<<endl;
////  }
////  return 0;
////}*/
/////*#include<cstdio>
////#include<cstring>
////#include<iostream>
////using namespace std;
////int v[1010][1010];
////int dis[1010][1010];
////char s[1010][1010];
////void dfs(int x,int y,int p,int q)
////{
////    if(v[x+1][y]==0&&s[x+1][y]=='.')
////    {
////        v[x+1][y]=1;
////        dis[p][q]++;
////        dfs(x+1,y,p,q);
////    }
////    if(v[x][y+1]==0&&s[x][y+1]=='.')
////    {
////        v[x][y+1]=1;
////        dis[p][q]++;
////        dfs(x,y+1,p,q);
////    }
////    if(v[x][y-1]==0&&s[x][y-1]=='.')
////    {
////        v[x][y-1]=1;
////        dis[p][q]++;
////        dfs(x,y-1,p,q);
////    }
////    if(v[x-1][y]==0&&s[x-1][y]=='.')
////    {
////        v[x-1][y]=1;
////        dis[p][q]++;
////
////        dfs(x-1,y,p,q);
////
////    }
////}
////int main()
////{
////    int n,m;
////    scanf("%d%d",&n,&m);
////    memset(dis,0,sizeof(dis));
////    memset(s,'*',sizeof(s));
////    for(int i=1; i<=n; i++)
////    {
////        for(int j=1; j<=m; j++)
////        {
////            cin>>s[i][j];
////        }
////    }
////    for(int i=1; i<=n; i++)
////    {
////        for(int j=1; j<=m; j++)
////        {
////            if(s[i][j]=='*')
////            {
////                memset(v,0,sizeof(v));
////                dfs(i,j,i,j);
////            }
////        }
////    }
////    for(int i=1; i<=n; i++)
////    {
////        for(int j=1; j<=m; j++)
////        {
////            if(s[i][j]=='*')
////            {
////                cout<<(dis[i][j]+1)%10;
////            }
////            else cout<<s[i][j];
////        }
////        cout<<endl;
////    }
////
////}*/
//////#include<cstdio>
//////#include<cstring>
//////#include<iostream>
//////using namespace std;
//////char  s[5][5];
//////int v[5][5];
//////int n;
//////int ans,sum;
//////int find(int x,int y)
//////{
//////    for(int i=y; i>=1; i--)
//////    {
//////        if(v[x][i]==1)
//////        {
//////            return 0;
//////        }
//////        if(v[x][i]==2)
//////        {
//////            break;
//////        }
//////    }
//////    for(int i=y; i<=n; i++)
//////    {
//////        if(v[x][i]==1)
//////        {
//////            return 0;
//////        }
//////        if(v[x][i]==2)
//////        {
//////            break;
//////        }
//////    }
//////    for(int i=x; i>=1; i--)
//////    {
//////        if(v[i][y]==1)
//////        {
//////            return 0;
//////        }
//////        if(v[i][y]==2)
//////        {
//////            break;
//////        }
//////    }
//////    for(int i=x; i<=n; i++)
//////    {
//////        if(v[i][y]==1)
//////        {
//////            return 0;
//////        }
//////        if(v[i][y]==2)
//////        {
//////            break;
//////        }
//////    }
//////    return 1;
//////}
//////void dfs()
//////{
//////    if(sum>ans)
//////        ans=sum;
//////    for(int i=1; i<=n; i++)
//////    {
//////        for(int j=1; j<=n; j++)
//////        {
//////            if(v[i][j]==0&&find(i,j))
//////            {
//////                v[i][j]=1;
//////                sum++;
//////                dfs();
//////                v[i][j]=0;
//////                sum--;
//////            }
//////        }
//////    }
//////}
//////int main()
//////{
//////
//////    while(~scanf("%d",&n)&&n)
//////    {
//////        memset(s,0,sizeof(s));
//////        memset(v,0,sizeof(v));
//////        for(int i=1;i<=n;i++)
//////        {
//////            for(int j=1;j<=n;j++)
//////            {
//////                cin>>s[i][j];
//////                if(s[i][j]=='X')
//////                    v[i][j]=2;
//////            }
//////        }
//////        sum=0,ans=-1;
//////        dfs();
//////        printf("%d\n",ans);
//////    }
//////
//////}
//////#include<stdio.h>
//////#include<string.h>
//////#define N 1000000+50
//////int a[N],b[N],v[N];
//////int Find(int x)
//////{
//////    int f=x;
//////    while(a[f]!=f)
//////        f=a[f];
//////    int i=x;
//////    while(i!=f)
//////    {
//////        int j=a[i];
//////        a[i]=f;
//////        i=j;
//////    }
//////    return f;
//////}
//////int main()
//////{
//////    int n,m;
//////    char s[3];
//////    int h=0;
//////    while(~scanf("%d%d",&n,&m))
//////    {
//////        int k=n;
//////        for(int i=0; i<n; i++)
//////            a[i]=i,b[i]=i;
//////        while(m--)
//////        {
//////            memset(s,0,sizeof(s));
//////            int p,q;
//////            scanf("%s",s);
//////            if(s[0]=='M')
//////            {
//////                scanf("%d%d",&p,&q);
//////                int xx=Find(b[p]);
//////                int yy=Find(b[q]);
//////                if(xx!=yy)
//////                {
//////                    a[xx]=yy;
//////                }
//////            }
//////            else
//////            {
//////                scanf("%d",&p);
//////                a[k]=k;
//////                b[p]=k;
//////                k++;
//////            }
//////        }
//////        memset(v,0,sizeof(v));
//////        int sum=0;
//////        for(int i=0;i<n;i++)
//////        {
//////            if(v[Find(b[i])]==0)
//////            {
//////                v[Find(b[i])]=1;
//////                sum++;
//////            }
//////        }
//////        printf("Case #%d: %d\n",++h,sum);
//////    }
//////}
//#include<stdio.h>
//#include<string.h>
//#define INF 0x3f3f3f3f
//#include<algorithm>
//#include<cmath>
//using namespace std;
//int dp[1000010];
//int a[3500];
//int main()
//{
//    int n,m,sum=0;
//    while(~scanf("%d%d",&n,&m))
//    {
//        memset(dp,0,sizeof(dp));
//        for(int i=1; i<=n; i++)
//        {
//            scanf("%d",&a[i]);
//            sum+=a[i];
//        }
//        for(int i=1; i<=n; i++)
//        {
//            for(int j=sum; j>=a[i]; j--)
//            {
//                dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
//            }
//        }
//        int mmin=1000000;
//        for(int i=sum;i>=m;i--)
//        {
//            if(dp[i]-m<mmin&&dp[i]-m>=0)
//                mmin=dp[i]-m;
//        }
//        printf("%d\n",mmin);
//    }
//    return 0;
//}
////
////
////
////#include<stdio.h>
////#include<string.h>
////int Max(int a,int b)
////{
////    return a>b?a:b;
////}
////int main()
////{
////    int t;
////    scanf("%d",&t);
////    while(t--)
////    {
////        int n,V;
////        int dp[1010],v[1010],s[1010];
////        scanf("%d%d",&n,&V);
////        for(int i=1;i<=n;i++)
////        {
////            scanf("%d",&s[i]);
////        }
////        for(int i=1;i<=n;i++)
////        {
////            scanf("%d",&v[i]);
////        }
////        memset(dp,0,sizeof(dp));
////        for(int i=1;i<=n;i++)
////        {
////            for(int j=V;j>=v[i];j--)
////            {
////                dp[j]=Max(dp[j],dp[j-v[i]]+s[i]);
////            }
////        }
////        printf("%d\n",dp[V]);
////    }
////}
////#include<cstdio>
////#include<cstring>
////#include<algorithm>
////using namespace std;
////int dp[31][510],n,m;
////void solve()
////{
////    int i,j,k;
////    for(i=n; i>=1; i--)
////    {
////        k=0;
////        for(j=m; j>=0; j--)
////            k+=dp[i][j];
////        if(k>0)
////        {
////            printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",k,i);
////            return;
////        }
////    }
////    printf("Sorry, you can't buy anything.\n");
////}
////int main()
////{
////    int t,i,j,k,p;
////    scanf("%d",&t);
////    while(t--)
////    {
////        scanf("%d%d",&n,&m);
////        memset(dp,0,sizeof(dp));
////        dp[0][0]=1;
////        for(i=1; i<=n; i++)
////        {
////            scanf("%d",&p);
////            for(j=m; j>=p; j--)
////                for(k=i; k>=1; k--)
////                    if(dp[k-1][j-p]>0)
////                        dp[k][j]+=dp[k-1][j-p];
////        }
////        solve();
////    }
////}
//#include<cstdio>
//#include<iostream>
//#include<queue>
//#include<cstring>
//using namespace std;
//char s[22][22];
//int v[22][22],vis[22][22];
//int b[130],c[130],d[130];
//int bx,by,n,m;
//int mov[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
//struct Node
//{
//    int x;
//    int y;
//};
//void  dfs(int x,int y)
//{
//    if(x-1>=0&&x<n&&y>=0&&y<m&&v[x-1][y]==0&&s[x-1][y]!='X')
//    {
//        v[x-1][y]=1;
//        if(s[x-1][y]>='A'&&s[x-1][y]<='E')
//        {
//
//            if(d[s[x-1][y]-'A']>0)
//            {
//                d[s[x-1][y]-'A']--;
//
//            }
//        }
//        if(s[x-1][y]>='a'&&s[x-1][y]<='e')
//        {
//            b[s[x-1][y]-'a']++;
//            d[s[x-1][y]-'a']++;
//        }
//        dfs(x-1,y);
//        v[x-1][y]=0;
//    }
//     if(x>=0&&x+1<n&&y>=0&&y<m&&v[x+1][y]==0&&s[x+1][y]!='X')
//    {
//        v[x+1][y]=1;
//        if(s[x+1][y]>='A'&&s[x+1][y]<='E')
//        {
//
//            if(d[s[x+1][y]-'A']>0)
//            {
//                d[s[x+1][y]-'A']--;
//
//            }
//        }
//        if(s[x+1][y]>='a'&&s[x+1][y]<='e')
//        {
//            b[s[x+1][y]-'a']++;
//            d[s[x+1][y]-'a']++;
//        }
//        dfs(x+1,y);
//        v[x+1][y]=0;
//    }
//     if(x>=0&&x<n&&y-1>=0&&y<m&&v[x][y-1]==0&&s[x][y-1]!='X')
//    {
//        v[x][y-1]=1;
//        if(s[x][y-1]>='A'&&s[x][y-1]<='E')
//        {
//
//            if(d[s[x][y-1]-'A']>0)
//            {
//                d[s[x][y-1]-'A']--;
//
//            }
//        }
//        if(s[x][y-1]>='a'&&s[x][y-1]<='e')
//        {
//            b[s[x][y-1]-'a']++;
//            d[s[x][y-1]-'a']++;
//        }
//        dfs(x,y-1);
//        v[x][y-1]=0;
//    }
//     if(x>=0&&x<n&&y>=0&&y+1<m&&v[x][y+1]==0&&s[x][y+1]!='X')
//    {
//        v[x][y+1]=1;
//        if(s[x][y+1]>='A'&&s[x][y+1]<='E')
//        {
//
//            if(d[s[x][y+1]-'A']>0)
//            {
//                d[s[x][y+1]-'A']--;
//
//            }
//        }
//        if(s[x][y+1]>='a'&&s[x][y+1]<='e')
//        {
//            b[s[x][y+1]-'a']++;
//            d[s[x][y+1]-'a']++;
//        }
//        dfs(x,y+1);
//        v[x][y+1]=0;
//    }
////    queue<Node>Q;
////    Node p,q;
////    p.x=bx;
////    p.y=by;
////    v[p.x][p.y]=1;
////    Q.push(p);
////    while(!Q.empty())
////    {
////        p=Q.front();
////        Q.pop();
////        for(int i=0; i<4; i++)
////        {
////            q.x=p.x+mov[i][0];
////            q.y=p.x+mov[i][1];
////            if(q.x>=0&&q.x<n&&q.y>=0&&q.y<m&&v[q.x][q.y]==0&&s[q.x][q.y]!='X')
////            {
////                if(s[q.x][q.y]=='.')
////                {
////                    printf("1\n");
////                    Q.push(q);
////                    v[q.x][q.y]=1;
////                }
////                if(s[q.x][q.y]>='A'&&s[q.x][q.y]<='E')
////                {
////                    printf("dsdas\n");
////                    if(d[s[q.x][q.y]-'A']>0)
////                    {
////                        d[s[q.x][q.y]-'A']--;
////                        Q.push(q);
////                        v[q.x][q.y]=1;
////                    }
////                }
////                if(s[q.x][q.y]>='a'&&s[q.x][q.y]<='e')
////                {
////                    printf("1111\n");
////                    b[s[q.x][q.y]-'a']++;
////                    d[s[q.x][q.y]-'a']++;
////                    Q.push(q);
////                    v[q.x][q.y]=1;
////                }
////            }
////        }
////    }
////    return -1;
//}
//int main()
//{
//    while(~scanf("%d%d",&n,&m)&&(n+m))
//    {
//        memset(v,0,sizeof(v));
//        memset(b,0,sizeof(b));
//        memset(c,0,sizeof(c));
//        for(int i=0; i<n; i++)
//        {
//            for(int j=0; j<m; j++)
//            {
//                cin>>s[i][j];
//                if(s[i][j]>='a'&&s[i][j]<='e')
//                {
//                    c[s[i][j]-'a']++;
//                }
//                if(s[i][j]=='S')
//                {
//                    bx=i;
//                    by=j;
//                }
//            }
//        }
//       dfs(bx,by);
//        memset(v,0,sizeof(v));
//        int f=0;
//        queue<Node>Q;
//        Node p,q;
//        p.x=bx;
//        p.y=by;
//        v[p.x][p.y]=1;
//        Q.push(p);
//        while(!Q.empty())
//        {
//            p=Q.front();
//            Q.pop();
//            if(s[p.x][p.y]=='G')
//            {
//                f=1;
//            }
//            for(int i=0; i<4; i++)
//            {
//                q.x=p.x+mov[i][0];
//                q.y=p.x+mov[i][1];
//                if(q.x>=0&&q.x<n&&q.y>=0&&q.y<m&&v[q.x][q.y]==0&&s[q.x][q.y]!='X')
//                {
//                    if(s[q.x][q.y]=='G'||(s[q.x][q.y]>='a'&&s[q.x][q.y]<='e'))
//                    {
//                        Q.push(q);
//                        v[q.x][q.y]=1;
//                    }
//                    if(s[q.x][q.y]>='A'&&s[q.x][q.y]<='E')
//                    {
//                        printf("%d %d !\n",b[s[q.x][q.y]],c[s[q.x][q.y]]);
//                        if(b[s[q.x][q.y]-'A']==c[s[q.x][q.y]-'A'])
//                        {
//
//                            Q.push(q);
//                            v[q.x][q.y]=1;
//                        }
//                    }
//                    if(s[q.x][q.y]=='.')
//                    {
//                        Q.push(q);
//                        v[q.x][q.y]=1;
//                    }
//                }
//            }
//        }
//        if(f==1)
//            printf("YES\n");
//        else printf("NO\n");
//
//    }
//}
//#include <stdio.h>
//#include <string.h>
//#include <algorithm>
//using namespace std;
//const int L = 1000005;
//int sum[L],s[L];
//
//int main()
//{
//    int n,m,a,i,j,k;
//    while(~scanf("%d%d",&n,&m))
//    {
//        sum[0] = s[0] = 0;
//        for(i = 1;i<=n;i++)
//        {
//            scanf("%d",&a);
//            sum[i]=sum[i-1]+a;
//            s[i]=s[i-1]+sum[i];
//        }
//        if(n<=m)
//        {
//            printf("%d\n",sum[n]);
//            continue;
//        }
//        int ans=0,maxn=0;
//        for(i=m;i<=n;i++)
//        {
//            ans = m*sum[i]-(s[i-1]-s[i-1-m]);
//            maxn = max(maxn,ans);
//        }
//        printf("%d\n",maxn);
//    }
//
//    return 0;
//}
//#include <iostream>
//#include<string>
//#include<cstring>
//#include <algorithm>
//#include <cstdio>
//using namespace std;
//int main()
//{
//    char s[1010];
//    int n;
//    while(~scanf("%s",s))
//    {
//        char ss[1010];
//        int b[1010],c[1010];
//        memset(b,0,sizeof(b));
//        memset(c,0,sizeof(c));
//        scanf("%d",&n);
//        int l=strlen(s);
//        int k=0,f=0;
//        for(int i=0; i<l; i++)
//            ss[i]=s[i];
//        for(int i=0; i<l; i++)
//        {
//            if(s[i]=='0')
//            {
//                k=i;
//                f=1;
//                break;
//            }
//        }
////        printf("%d !\n",k);
//        sort(s,s+l);
//        if(f)
//        {
//            if(n>0)
//            {
//                for(int i=l-1; i>=0; i--)
//                {
//                    if(c[i]==0)
//                    {
//                        for(int j=0; j<k; j++)
//                        {
//                            if(b[j]==0&&s[i]!='0'&&ss[j]!='0'&&s[i]==ss[j])
//                            {
//                                b[j]=1;
//                                c[i]=1;
//                                n--;
//                                if(n<=0)
//                                    break;
//                            }
//                        }
//                        if(n<=0)
//                            break;
//                    }
//                }
//            }
//            if(n>0)
//            {
//                for(int i=l-1; i>=0; i--)
//                {
//                    if(c[i]==0)
//                    {
//                        for(int j=k; j<l; j++)
//                        {
//                            //printf("%c %c !!!\n",s[i],ss[j]);
//                            if(b[j]==0&&s[i]!='0'&&ss[j]!='0'&&s[i]==ss[j])
//                            {
//                                //printf("%c %d  ##\n",ss[j],j);
//                                b[j]=1;
//                                c[i]=1;
//                                n--;
//                                if(n<=0)
//                                    break;
//                            }
//                        }
//                        if(n<=0)
//                            break;
//                    }
//                }
//            }
//            int p=-1;
//            for(int i=0; i<l; i++)
//            {
//                if(ss[i]!='0'&&b[i]==0)
//                {
//                    p=i;
//                    break;
//                }
//            }
//            if(p==-1)
//            {
//                printf("0\n");
//            }
//            else
//            {
//                for(int i=p; i<l; i++)
//                {
//                    if(!b[i])
//                        printf("%c",ss[i]);
//                }
//                printf("\n");
//            }
//        }
//        else
//        {
//            for(int i=l-1; i>=0; i--)
//            {
//                for(int j=0; j<l; j++)
//                {
//                    if(b[j]==0&&s[i]==ss[j])
//                    {
//                        // printf("%c %d !\n",ss[j],j);
//                        b[j]=1;
//                        n--;
//                        if(n<=0)
//                            break;
//                    }
//                }
//                if(n<=0)
//                    break;
//            }
//            for(int i=0; i<l; i++)
//            {
//                if(!b[i])
//                {
//                    printf("%c",ss[i]);
//                }
//
//            }
//            printf("\n");
//        }
//        memset(s,0,sizeof(s));
//
//    }
//}
//#include <cstdio>
//const int maxm = 2005, mod = 1e9+7;
//long long dp[maxm][4];
//int main (void)
//{
//    int T;            //  数位DP
//    scanf("%d",&T);
//    dp[0][1] = 26;
//    for(int i = 1; i < 2005; i++)
//    {
//        dp[i][2] = dp[i - 1][1]%mod;
//        dp[i][3] = dp[i - 1][2]%mod;
//        dp[i][1] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) %mod * 25;
//    }
//    while(T--)
//    {
//        int n;
//        scanf("%d",&n);
//        printf("%d\n",(dp[n - 1][1] + dp[n - 1][2] + dp[n - 1][3])%mod);
//    }
//}
//#include<stdio.h>
//#include<string.h>
//struct seg
//{
//    int l;
//    int r;
//    int n;
//} T[150011];
//void build(int l,int r,int k)
//{
//    int mid;
//    if(l==r)
//    {
//        T[k].l=l;
//        T[k].r=r;
//        T[k].n=0;
//        return ;
//    }
//    mid=(l+r)/2;
//    T[k].l=l;
//    T[k].r=r;
//    T[k].n=0;
//    build(l,mid,2*k);
//    build(mid+1,r,2*k+1);
//}
//void insert(int n,int d,int k)
//{
//    int mid;
//    if(T[k].l==T[k].r&&T[k].l==d)
//    {
//        T[k].n+=n;
//        return ;
//    }
//    mid=(T[k].l+T[k].r)>>1;
//    if(d<=mid)   insert(n,d,2*k);
//    else        insert(n,d,2*k+1);
//    T[k].n=T[2*k].n+T[2*k+1].n;
//}
//
//int ans;
//void search(int l,int r,int k)
//{
//    int mid;
//    if(T[k].l==l&&T[k].r==r)
//    {
//        ans+=T[k].n;
//        return ;
//    }
//    mid=(T[k].l+T[k].r)>>1;
//    if(r<=mid)
//        search(l,r,2*k);
//    else if(l>mid)
//        search(l,r,2*k+1);
//    else
//    {
//        search(l,mid,2*k);
//        search(mid+1,r,2*k+1);
//    }
//}
//
//
//int main()
//{
//    int Case,TT;
//    int n;
//    int i;
//    int temp;
//    char str[11];
//    int a,b;
//    scanf("%d",&TT);
//    for(Case=1; Case<=TT; Case++)
//    {
//        scanf("%d",&n);
//        build(1,n,1);
//        for(i=1; i<=n; i++)
//        {
//            scanf("%d",&temp);
//            insert(temp,i,1);
//        }
//        printf("Case %d:\n",Case);
//        while(scanf("%s",str)&&str[0]!='E')
//        {
//            scanf("%d%d",&a,&b);
//            if(str[0]=='A')
//                    insert(b,a,1);
//            else if(str[0]=='S')
//             insert(-b,a,1);
//            else
//            {
//                ans=0;
//                search(a,b,1);
//                printf("%d\n",ans);
//            }
//        }
//    }
//    return 0;
//}
//#include <iostream>
//#include <stdio.h>
//#include <vector>
//using namespace std;
//vector<int>a[100005];
//int b[100005],n,s;
//void dfs(int x,int y)
//{
//    for (int i=0; i<a[x].size();i++)
//    {
//        //printf("%d !\n",a[x][i]);
//        if (a[x][i]!= y)
//            dfs(a[x][i],b[a[x][i]]=x);
//    }
//    return;
//}
//int main()
//{
//    int k,x,y;
//    scanf("%d",&k);
//    while (k--)
//    {
//        scanf("%d%d",&n,&s);
//        for (int i = 1; i <n; i++)
//        {
//            a[i].clear();
//        }
//        for (int i = 1; i <n; i++)
//        {
//            scanf("%d%d",&x,&y);
//            a[x].push_back(y);
//            a[y].push_back(x);
//        }
//        b[s]=-1;
//        dfs(s,-1);
//        for (int i = 1; i <= n; i++)
//            printf("%d ",b[i]);
//        printf("\n");
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<string.h>
//struct tt
//{
//    int l;
//    int r;
//    int n;
//}T[150011];
//void build(int l,int r,int k)
//{
//    int mid;
//    if(l==r)
//    {
//        T[k].l=l;
//        T[k].r=r;
//        T[k].n=0;
//        return ;
//    }
//    mid=(l+r)/2;
//    T[k].l=l;
//    T[k].r=r;
//    T[k].n=0;
//    build(l,mid,2*k);
//    build(mid+1,r,2*k+1);
//}
//void updata(int n,int d,int k)
//{
//    int mid;
//    if(T[k].l==T[k].r&&T[k].l==d)
//    {
//        T[k].n+=n;
//        return ;
//    }
//    mid=(T[k].l+T[k].r)>>1;
//    if(d<=mid) updata(n,d,2*k);
//    else updata(n,d,2*k+1);
//    T[k].n=T[2*k].n+T[2*k+1].n;
//}
//int ans;
//void query(int l,int r,int k)
//{
//    int mid;
//    if(T[k].l==l&&T[k].r==r)
//    {
//        ans+=T[k].n;
//        return ;
//    }
//    mid=(T[k].l+T[k].r)>>1;
//    if(r<=mid)
//    {
//        query(1,r,2*k);
//    }
//    else if(l>mid)
//    {
//        query(l,r,2*k+1);
//    }
//    else
//    {
//        query(l,mid,2*k);
//        query(mid+1,r,2*k+1);
//    }
//}
//int main()
//{
//    int Case,TT;
//    int n;
//    int temp;
//    char str[11];
//    int a,b;
//    scanf("%d",&TT);
//    for(Case=1;Case<=TT;Case++)
//    {
//        scanf("%d",&n);
//        build(1,n,1);
//        for(int i=1;i<=n;i++)
//        {
//            scanf("%d",&temp);
//            updata(temp,i,1);
//        }
//        printf("Case %d:\n",Case);
//        while(~scanf("%s",str)&&str[0]!='E')
//        {
//            scanf("%d%d",&a,&b);
//            if(str[0]=='A')
//            {
//                updata(b,a,1);
//            }
//            else if(str[0]=='S')
//            {
//                updata(-b,a,1);
//            }
//            else
//            {
//                ans=0;
//                query(a,b,1);
//                printf("%d\n",ans);
//            }
//        }
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<string.h>
//struct seg
//{
//    int l;
//    int r;
//    int n;
//} T[150011];
//void build(int l,int r,int k)
//{
//    int mid;
//    if(l==r)
//    {
//        T[k].l=l;
//        T[k].r=r;
//        T[k].n=0;
//        return ;
//    }
//    mid=(l+r)/2;
//    T[k].l=l;
//    T[k].r=r;
//    T[k].n=0;
//    build(l,mid,2*k);
//    build(mid+1,r,2*k+1);
//}
//void updata(int n,int d,int k)
//{
//    int mid;
//    if(T[k].l==T[k].r&&T[k].l==d)
//    {
//        T[k].n+=n;
//        return ;
//    }
//    mid=(T[k].l+T[k].r)>>1;
//    if(d<=mid)   updata(n,d,2*k);
//    else        updata(n,d,2*k+1);
//    T[k].n=T[2*k].n+T[2*k+1].n;
//}
//
//int ans;
//void query(int l,int r,int k)
//{
//    int mid;
//    if(T[k].l==l&&T[k].r==r)
//    {
//        ans+=T[k].n;
//        return ;
//    }
//    mid=(T[k].l+T[k].r)>>1;
//    if(r<=mid)
//       query(l,r,2*k);
//    else if(l>mid)
//        query(l,r,2*k+1);
//    else
//    {
//        query(l,mid,2*k);
//        query(mid+1,r,2*k+1);
//    }
//}
//
//
//int main()
//{
//    int Case,TT;
//    int n;
//    int i;
//    int temp;
//    char str[11];
//    int a,b;
//    scanf("%d",&TT);
//    for(Case=1; Case<=TT; Case++)
//    {
//        scanf("%d",&n);
//        build(1,n,1);
//        for(i=1; i<=n; i++)
//        {
//            scanf("%d",&temp);
//            updata(temp,i,1);
//        }
//        printf("Case %d:\n",Case);
//        while(scanf("%s",str)&&str[0]!='E')
//        {
//            scanf("%d%d",&a,&b);
//            if(str[0]=='A')
//                    updata(b,a,1);
//            else if
//                (str[0]=='S')
//             updata(-b,a,1);
//            else
//            {
//                ans=0;
//                query(a,b,1);
//                printf("%d\n",ans);
//            }
//        }
//    }
//    return 0;
//}
//#include <stdio.h>
//#include <string.h>
//#include <algorithm>
//using namespace std;
//const int maxn=100000+10;
//int n,m,sum;
//struct node
//{
//    int l,r;
//    int n,sum;
//}a[maxn<<2];
//void init(int l,int r,int i)
//{
//    a[i].l = l;
//    a[i].r = r;
//    a[i].n = 0;
//    a[i].sum = 0;
//    if(l!=r)
//    {
//        int mid = (l+r)>>1;
//        init(l,mid,2*i);
//        init(mid+1,r,2*i+1);
//    }
//}
//void insert(int i,int l,int r,int m)
//{
//    a[i].n+=(r-l+1)*m;
//    if(a[i].l >= l && a[i].r <= r)
//        a[i].sum+=m;
//    else
//    {
//        int mid = (a[i].l+a[i].r)>>1;
//        if(r<=mid)
//            insert(2*i,l,r,m);
//        else if(l>mid)
//            insert(2*i+1,l,r,m);
//        else
//        {
//            insert(2*i,l,mid,m);
//            insert(2*i+1,mid+1,r,m);
//        }
//    }
//}
//int find(int i,int l,int r)
//{
//    if(a[i].l==l&&a[i].r == r)
//        return a[i].n;
//    else
//    {
//        int mid = (a[i].l+a[i].r)>>1;
//        if(a[i].sum)
//        {
//            a[2*i].sum+= a[i].sum;
//            a[2*i].n+=a[i].sum*(a[2*i].r-a[2*i].l+1);
//            a[2*i+1].sum += a[i].sum;
//            a[2*i+1].n+=a[i].sum*(a[2*i+1].r-a[2*i+1].l+1);
//            a[i].sum=0;
//        }
//        if(r<=mid)
//            return find(2*i,l,r);
//        else if(l>mid)
//            return find(2*i+1,l,r);
//        else
//        {
//            return find(2*i,l,mid)+find(2*i+1,mid+1,r);
//        }
//    }
//}
//int main()
//{
//    int i,j,x,y,q;
//    int k;
//    char str[5];
//    while(~scanf("%d%d%d",&n,&m,&q))
//    {
//        init(1,n,1);
//        for(i = 1; i<=n; i++)
//        {
//            scanf("%d",&k);
//            insert(1,i,i,k);
//        }
//        while(q--)
//        {
//            scanf("%d",&x);
//            printf("%d\n", find(1,x,x+m-1));
//            insert(1,x,x+m-1,-1);
//        }
//    }
//    return 0;
//}
//#include <cstdio>
//#include <cstring>
//const int maxn=50001;
//int dp[maxn];
//int max(int a,int b)
//{
//    return a>b?a:b;
//}
//int main()
//{
//    int n,m,v,i,j,c,w;
//    scanf("%d",&n);
//    while(n--)
//    {
//      memset(dp,-10000,sizeof(dp));
//      dp[0]=0;
//      scanf("%d%d",&m,&v);
//      for(i=1;i<=m;i++)
//      {
//          scanf("%d%d",&c,&w);
//          for(j=c;j<=v;j++)
//                dp[j]=max(dp[j],dp[j-c]+w);
//      }
//      if(dp[v]<0) printf("NO\n");
//       else  printf("%d\n",dp[v]);
//    }
//    return 0;
//}
//#include<stdio.h>
//#include<string.h>
//#include<algorithm>
//#include<iostream>
//using namespace std;
//int main()
//{
//    int n,i,j,k;
//    int a[1111],ss[1111];
//    while(~scanf("%d",&n))
//    {
//        memset(a,0,sizeof(a));
//        memset(ss,0,sizeof(ss));
//        for(i=0; i<n; i++)
//            ss[i]=i+1;
//        for(i=0; i<n; i++)
//            cin>>a[i];
//        for(i=0; i<n; i++)
//        {
//            sort(ss,ss+n);
//            if(i!=n-1)
//            {
//                printf("%d ",ss[a[i]]);
//                ss[a[i]]=n+1;
//            }
//            else printf("%d\n",ss[a[i]]);
//        }
//    }
//}
//#include<cstring>
//#include<cstdio>
//#include<queue>
//#include<iostream>
//using namespace std;
//char s[333][333];
//int vis[333][333];
//int mov[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//int bx,by,ex,ey;
//int n,m;
//struct node
//{
//    int x;
//    int y;
//    int step;
//    bool friend operator <(node a,node b)
//    {
//        return a.step>b.step;
//    }
//};
//int bfs()
//{
//    priority_queue<node>Q;
//    node p,q;
//    p.x=bx;
//    p.y=by;
//    p.step=0;
//    vis[bx][by]=1;
//    Q.push(p);
//    while(!Q.empty())
//    {
//        p=Q.top();
//        Q.pop();
//        if(p.x==ex&&p.y==ey)
//        {
//            return p.step;
//        }
//        for(int i=0;i<4;i++)
//        {
//            int xx=p.x+mov[i][0];
//            int yy=p.y+mov[i][1];
//            if(xx>=0&&xx<n&&yy>0&&yy<m&&vis[xx][yy]==0&&s[xx][yy]!='R'&&s[xx][yy]!='S')
//            {
//
//                if(s[xx][yy]=='E')
//                {
//                    q.x=xx;
//                    q.y=yy;
//                    q.step=p.step+1;
//                    Q.push(q);
//                    vis[xx][yy]=1;
//                }
//                else if(s[xx][yy]=='B')
//                {
//                    q.x=xx;
//                    q.y=yy;
//                    q.step=p.step+2;
//                    Q.push(q);
//                     vis[xx][yy]=1;
//                }
//                else if(s[xx][yy]=='T')
//                {
//                     q.x=xx;
//                    q.y=yy;
//                    q.step=p.step+1;
//                    Q.push(q);
//                     vis[xx][yy]=1;
//                }
//            }
//        }
//    }
//    return -1;
//}
//int main()
//{
//    while(~scanf("%d%d",&n,&m)&&(n+m))
//    {
//        getchar();
//        memset(s,0,sizeof(s));
//        memset(vis,0,sizeof(vis));
//        for(int i=0;i<n;i++)
//        {
//            for(int j=0;j<m;j++)
//            {
//                cin>>s[i][j];
//                if(s[i][j]=='Y')
//                {
//                    bx=i;
//                    by=j;
//                }
//                if(s[i][j]=='T')
//                {
//                    ex=i;
//                    ey=j;
//                }
//            }
//        }
//        printf("%d\n",bfs());
//    }
//}
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
using namespace std;
const long long  MAX = (long long)1e5 + 5;
const long long mod=1e9+7;
long long  n,k;
long long  h[MAX];
long long  ans;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
       scanf("%I64d%I64d",&n,&k);
        ans=1;
        if(n<(1+k)*k/2) printf("-1\n");
        else
        {
            for(int i=1; i<=k; i++)
            {
                h[i]=i;
            }
            n=n-(1+k)*k/2;
            long long  a=n/k;
           long long b=n%k;
            for(int i=k; i>=1; i--)
            {
                if(b>0)
                {
                    ans*=((h[i]+1+a)%mod);
                    ans%=mod;
                    b--;
                }
                else
                {
                    ans*=((h[i]+a)%mod);
                    ans%=mod;
                }
            }
            printf("%I64d\n",ans);
        }
    }
    return 0;
}