//分解质因数
#include <iostream>
using namespace std;
int n,a;
void panduan(int &a){
    for(int i=2; i<=a/i; i++){
        if(a%i==0){
            int num=0;
            while(a%i==0){
                a/=i;
                num++;
            }
            cout<<i<<' '<<num<<endl;
        }
    }
    if(a>1)cout<<a<<' '<<1<<endl;
    return;
}
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a;
        panduan(a);
        cout<<endl;
    }
    return 0;
}

//试除法求约数
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int>v;
void get(int a){
    for(int i=1; i*i<=a; i++){
        if(a%i==0){
            v.push_back(i);
            if(i*i!=a)v.push_back(a/i);
        }
    }
    sort(v.begin(),v.end());
    for(auto t:v)cout<<t<<' ';
    cout<<endl;
}
int main(){
    cin>>n;
    while(n--){
        int a;
        cin>>a;
        get(a);
        v.clear();
    }
    return 0;
}
//约数个数
#include <iostream>
#include <unordered_map>
using namespace std;
const int mod=1e9+7;
typedef long long LL;
int n;
int main(){
    cin>>n;
    unordered_map<int,int>hash;
    while(n--){
        int a;
        cin>>a;
        for(int i=2; i<=a/i; i++){
            while(a%i==0){
                hash[i]++;
                a/=i;
            }
        }
        if(a>1)hash[a]++;
    }
    LL ans=1;
    for(auto t: hash){
        ans=ans*(t.second+1)%mod;
    }
    cout<<ans;
    return 0;
}
//约数之和
#include <iostream>
#include <unordered_map>
using namespace std;
const int mod=1e9+7;
typedef long long LL;
int n;
int main(){
    cin>>n;
    unordered_map<int,int>hash;
    while(n--){
        int a;
        cin>>a;
        for(int i=2; i<=a/i; i++){
            while(a%i==0){
                hash[i]++;
                a/=i;
            }
        }
        if(a>1)hash[a]++;
    }
    LL ans=1;
    for(auto t: hash){
        int a=t.first,b=t.second;
        LL s=1;
        while(b--)s=(s*a+1)%mod;

        ans=(ans*s)%mod;
    }
    cout<<ans;
    return 0;
}
//最大公约数
#include <iostream>
using namespace std;
int gcd(int a,int b){
    return b?gcd(b,a%b): a;
}
int main(){
    int n;
    cin>>n;
    while(n--){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;}
    return 0;
}

//求组合数 II
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++ )
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}

//并查集
#include <iostream>
using namespace std;
const int maxn=1e5+10;
int m,n;
int p[maxn],cnt[maxn];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    cin>>n>>m;

    for(int i=1; i<=n; i++){
        p[i]=i;
        cnt[i]=1;
    }
    while(m--){
        string op;
        int a,b;
        cin>>op;
        if(op=="C"){
            cin>>a>>b;
            a=find(a),b=find(b);
            if(a!=b){
                p[a]=b;
                cnt[b]+=cnt[a];
            }
        }else if(op=="Q1"){
            cin>>a>>b;
            if(find(a)==find(b)){
                cout<<"Yes"<<endl;
            }else cout<<"No"<<endl;
        }else {
            cin>>a;
            cout<<cnt[find(a)]<<endl;
        }
    }
    return 0;
}
//石子合并
#include <iostream>
#include <algorithm>
const int maxn=1010;
using namespace std;
int shuzu[maxn];
int f[maxn][maxn];
int n;
int main(){
    cin>>n;
    for(int i=1 ;i<=n; i++)cin>>shuzu[i];
    for(int i=1; i<=n; i++)shuzu[i]+=shuzu[i-1];

    for(int len=2; len<=n; len++){//枚举石子长度
        for(int l=1; l+len-1<=n; l++){//枚举长度为len的所有区间！注意需要i+len-1比如长度是2就是1到2共两个点
            int r=l+len-1;//区间左端点和右端点
            f[l][r]=1e9;//初始区间没合并的时候选无穷大
            for(int k=l; k<r; k++){
                f[l][r]=min(f[l][r], f[l][k]+f[k+1][r]+shuzu[r]-shuzu[l-1]);
            }
        }
    }
    printf("%d", f[1][n]);
    return 0;
}
//日期
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
string a,b;
int n; 
void f(string a,string b){
    if(a[a.size()-1]!=')')a+=" (+0)";
    if(b[b.size()-1]!=')')b+=" (+0)";
    int aa,bb;
    int ah,am,as,bh,bm,bs,bd;
    sscanf(a.c_str(),"%d:%d:%d %d:%d:%d (%d)",&ah,&am,&as,&bh,&bm,&bs,&bd);
    aa=bh*3600+bm*60+bs-(ah*3600+am*60+as)+bd*24*3600;
    sscanf(b.c_str(),"%d:%d:%d %d:%d:%d (%d)",&ah,&am,&as,&bh,&bm,&bs,&bd);
    bb=bh*3600+bm*60+bs-(ah*3600+am*60+as)+bd*24*3600;
    int cc=(aa+bb)/2;
    printf("%02d:%02d:%02d\n",cc/3600,cc%3600/60,cc%60);
}
int main(){
    cin>>n;
    string aaa;
    getline(cin,aaa);
    for(int i=0; i<n; i++){
        getline(cin,a);
        getline(cin,b);
        f(a,b);
    }
    return 0;
}
//十三号星期五
#include <iostream>
#include <algorithm>
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int weekday[7];

int getyear(int year,int m){
    if(m!=2)return months[m];
    if(year%4==0 && year%100 || year%400==0)return 29;
    else return 28;
}
int main(){
    int n;
    cin>>n;
    int week=0;
    int year=1900,month=1,day=1;
    while(year<1900+n){
        if(day==13)weekday[week]++;
        week=(week+1)%7;
        day++;
        if(day>getyear(year,month)){
            day=1;
            month++;
        }
        if(month>12){
            month=1;
            year++;
        }
    }
    for(int i=5,j=0;j<7; j++,i=(i+1)%7){
        cout<<weekday[i]<<" ";
    }
    return 0;
}

//子矩阵和
#include <iostream>
using namespace std;
int n,m,q;
const int maxn=1010;
int a[maxn][maxn];
int s[maxn][maxn];
int main(){
    cin>>n>>m>>q;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>s[i][j];
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    while(q--){
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    return 0;
}
//走迷宫
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
const int maxn=110;
int a[maxn][maxn],d[maxn][maxn];
int m,n;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool st[maxn][maxn];
queue<PII>q;
void bfs(int x,int y){
    q.push({x,y});
    while(q.size()){
        auto t=q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int x1=t.first+dx[i],y2=t.second+dy[i];
            if(x1>=1&&x1<=m&&y2>=1&&y2<=n&&!st[x1][y2]&&a[x1][y2]!=1){
                q.push({x1,y2});
                st[x1][y2]=true;
                d[x1][y2]=d[t.first][t.second]+1;
            }
        }
    } 
}
int main(){
    cin>>m>>n;
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            cin>>a[i][j];
        }
    }
    bfs(1,1);
    cout<<d[m][n];
    return 0;
}
//01背包
#include <iostream>
using namespace std;
const int maxn=1010;
int m,n;
int w[maxn],v[maxn];
int dp[maxn];
int main(){
    cin>>m>>n;
    for(int i=1; i<=m; i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1; i<=m; i++){
        for(int j=n; j>=v[i]; j--){
            dp[j]=max(dp[j], dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[n];
    return 0;
}
//完全背包
#include <iostream>
using namespace std;
int n,V;
const int maxn=1e3+10;
int v[maxn],w[maxn];
int dp[maxn]; 
int main(){
    cin>>n>>V;
    for(int i=1; i<=n; i++){
        cin>>v[i]>>w[i];
    }
    for(int i=1; i<=n; i++){
        for(int j=v[i]; j<=V; j++){
            dp[j]=max(dp[j], dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V];
    return 0;
}
//多重背包
#include <iostream>
using namespace std;
const int maxn=25100;
int dp[maxn];
int v[maxn],w[maxn];
int n,V;
int main(){
    cin>>n>>V;
    int a,b,s;
    int cnt=0;
    for(int i=1; i<=n; i++){
        cin>>a>>b>>s;
        int k=1;
        while(s>=k){
            cnt++;
            v[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
        }
        if(s>0){
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
    }
    for(int i=1; i<=cnt; i++){
        for(int j=V; j>=v[i]; j--){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V];
    return 0;
}
//筛质数
#include <iostream>
using namespace std;
const int maxn=1e6+10;
bool st[maxn];
int main(){
    int n;
    cin>>n;
    for(int i=2; i<maxn; i++){
        for(int j=i+i; j<maxn; j+=i){
            st[j]=true;
        }
    }

//池塘计数
#include <iostream>
using namespace std;
const int maxn=1010;
char s[maxn][maxn];
int m,n;
int ans=0;
void dfs(int a,int b){
    s[a][b]='#';
    for(int i=a-1;i<=a+1; i++){
        for(int j=b-1; j<=b+1; j++){
            if(i==a&&j==b)continue;
            if(i<0||i>=m||j<0||j>=n){
                continue;
            }
            if(s[i][j]=='W')dfs(i,j);
        }
    }
}
int main(){
    cin>>m>>n;
    for(int i=0; i<m; i++){
        scanf("%s",s[i]);
    }
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(s[i][j]=='W'){
                ans++;
                dfs(i,j);
            }
        }
    }
    cout<<ans;
    return 0;
}
//方格取数
#include <iostream>
using namespace std;
const int maxn =100;
int a[maxn][maxn];
int dp[maxn][maxn][maxn*2];
int n;
int main(){
    cin>>n;
    int x,y,z;
    while(cin>>x>>y>>z, x&&y&&z)a[x][y]=z;

    for(int k=2; k<=2*n; k++){
        for(int i1=1; i1<=k; i1++){
            for(int i2=1; i2<=k; i2++){
                int j1=k-i1;
                int j2=k-i2;
                int t=a[i1][j1];
                if(i1!=i2){
                    t+=a[i2][j2];
                }
                dp[i1][i2][k]=max(dp[i1][i2][k], dp[i1-1][i2][k-1]+t);
                dp[i1][i2][k]=max(dp[i1][i2][k], dp[i1-1][i2-1][k-1]+t);
                dp[i1][i2][k]=max(dp[i1][i2][k], dp[i1][i2-1][k-1]+t);
                dp[i1][i2][k]=max(dp[i1][i2][k], dp[i1][i2][k-1]+t);
            }
        }
    }
    cout<<dp[n][n][2*n];
    return 0;
}

//二维前缀和

include [HTML_REMOVED]

using namespace std;
int n,m,q;
const int maxn=1010;
int a[maxn][maxn];
int s[maxn][maxn];
int main(){
cin>>n>>m>>q;
for(int i=1; i<=n; i){
for(int j=1; j<=m; j){
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
while(q–){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}
return 0;
}
//一维前缀和

#include <iostream>
using namespace std;
const int maxn=100010;
int a[maxn];
int n,m;
int num;
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }

    while(m--){
        int a1,b1;
        cin>>a1>>b1;
        cout<<a[b1]-a[a1-1]<<endl;
    }

    return 0;
}