#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e4+10;
typedef pair<int,int> PII;
int n;
PII cow[N];

int main(){
    cin >>n;
    for(int i = 0 ; i <n ; i ++){
        int s,w;
        cin >> w >>s ;
        cow[i] = {s+w,w} ;//s是强壮程度
    }
    sort(cow,cow+n);
    int res = -2e9 , sm = 0;//sum是头上摞的全部重量 res是危险值
    for(int i = 0 ; i < n ; i ++){
        int s = cow[i].first - cow[i].second , w = cow[i].second;
        res = max(res ,sm-s);
        sm += w;
    }
    cout << res;
    return 0;
}

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l,r;
    bool operator <(const Range &W)const{
        return l < W.l;
    }
}range[N];

int main(){
    int st,ed;
    cin >> st>> ed;
    cin >> n;
    for(int i = 0 ; i < n ; i ++) cin >> range[i].l >> range[i].r;
    sort(range,range+n);
    int res = 0;
    bool success = false;
    for(int i = 0 ; i < n ; i ++){
        int j = i , r = -2e9;
        while(j < n && range[j].l <= st){//如果j小于n个区间且当前区间的左端点在起点前
            r = max(range[j].r,r);//右端点就找最长的那个
            j++;
        }
        if(r < st){//如果当前区间的右端点够不到下个区间的起点 必然不能覆盖
            res = -1;
            break;
        }
        res++;//找到一个
        if(r >= ed){//正确出for循环条件:只有右端点大于终点 才能覆盖 正确出去
            success = true;
            break;
        }
        st = r;//把这一轮的判断区间的右端点视作下一轮的起点
        i = j - 1;//下一轮可以直接从j-1个判断 已经排序过了
    }
    if(!success) res = -1;
    cout << res<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l,r;
    bool operator <(const Range &W)const{
        return l < W.l;
    }
}range[N];

int main(){
    cin >>n;
    for(int i = 0 ; i < n ; i ++) cin >> range[i].l >> range[i].r;
    sort(range , range + n);
    priority_queue<int , vector<int>,greater<int>> heap;//heap里是每组中区间们的最右端点 
    for(int i = 0 ; i < n ; i ++){
        if(heap.empty() || heap.top() >= range[i].l )//range[i].l才是要判断的区间
            heap.push(range[i].r);//top只会放区间们的右端点 右端点>=左端点->有交集
        else {
            heap.pop();//上面的情况是有交集 在这里就是无交集 往已有的组里加一个新区间就行 不要开新组
            heap.push(range[i].r);
        }
    }
    cout << heap.size() <<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l,r;
    bool operator <(const Range &C)const{
        return r < C.r;
    }
}range[N];

int main(){
    cin >> n;
    for(int i = 0 ; i < n ; i ++) cin >> range[i].l >> range[i].r;
    sort(range,range + n);
    int res = 0 , ed = -2e9;
    for(int i= 0 ; i < n ; i ++)//遍历每个输入的区间
        if(range[i].l > ed){//如果新的这个区间和前一个区间没有交集
            res ++ ;//需要多一个点
            ed = range[i].r;//把判定点改成新区间的右端点
        }
    cout << res << endl;
    return 0;
}

/*
    找<a[i]的q中的最大的数 若q[mid] < a[i] a[i]就可以加到q后面了
    r是可以接到某个长度的后面
*/
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N],q[N];//q的意思是当序列长度为i时，q[i]是序列结尾的最小值

int main(){
    cin >>n;
    for(int i  = 1;i <= n ; i ++) cin >> a[i];
    int len = 0;//前i个数中最大的最长上升子序列的值
    for(int  i = 1 ; i <= n ; i ++){
        int l = 0, r = len;
        while(l < r){//在q中二分查找比a[i]小的最大的那个值 说明这个数应该加到这个q[i]的后面 而且要i+=1
            int mid = l + r + 1 >> 1;
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len,  r+ 1);//while循环后 q[len]一定<a[i] 但如果找不到==a[i]>q[len]->a[i]要在q[len]后 len+1
        q[r+ 1] = a[i];//q[r]已经一定小于a[i]了 所以q[r+1]一定大于a[i] 就把a[i]插入到q[r]后面 q[r+1]就=a[i]
    }
    cout << len;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 10010, INF = 1e9;
int n,m;
int a[N][N];
int f[N][N];

int main(){
    cin >>n;
    for(int i = 1;i <= n ; i ++)
        for(int  j = 1 ; j <= i ; j ++)
            cin >> a[i][j] ;
    for(int i = 0; i <= n ; i ++)
        for(int j = 0 ; j <= i + 1 ; j ++)//三角形的右边们会往右上去探索一条不存在的路径 所以每一行尾+1也赋值
            f[i][j] = -INF;
    f[1][1] = a[1][1];

    for(int i = 2; i <= n ; i ++)//第一行已经是a[1][1]确定了 所以从第二行开始做
        for(int j = 1; j <= i ;j ++)
            f[i][j] = max(f[i-1][j-1] + a[i][j], f[i-1][j]+a[i][j] );
    int res = -INF;
    for(int i = 1; i <= n ; i ++) res = max(res,f[n][i]);
    cout <<res <<endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;
const int N = 110;
const double eps = 1e-8;
double a[N][N];
int n;

int gauss(){//答案存在a[i][n]中
    int c,r;//列 行
    for(c = 0 ,r = 0;c < n ;c ++){//从第1列开始遍历
        int t =r ;//t是行指针
        for(int i = r ; i < n; i ++)//先遍历行
            if(fabs(a[i][c]) > fabs(a[t][c]))//如果某一行第一列的绝对值 大于 第一行第一列的绝对值
                t = i;//那让t指向那一行
        if(fabs(a[t][c]) < eps) continue;//如果第一行就是最大了但还是0 跳过

        for(int i = c;i <= n; i++) swap(a[t][i],a[r][i]);//从第一列开始遍历 把那一行的数据换到第一行
        for(int i = n;i >= c; i--) a[r][i] /= a[r][c];//把那一行的数据全部除以那一行第一个的值 让第一个值变1
        for(int i = r + 1; i < n;i++)//用当前行把下面变0
            if(fabs(a[i][c]) > eps) //如果这一行第一个不是0 才要变成0
                for(int j = n ; j >= c; j--)//从这一行的最后一列开始往前走
                    a[i][j] -= a[r][j] * a[i][c];//当前列的每个值变成 每个值-(上一行这一列(1)*这一行第一列)

        r++;//循环处理到下一行
    }

    if(r < n){//因为方程数量小于n 说明不是唯一解
        for(int i = r; i < n ;i++)
            if(fabs(a[i][n]) > eps)//因为已经是阶梯型 =左边已经全是0了 右边如果不是0 就出现 0=!0 
                return 2;//无解
        return 1;//如果都是0 就有无穷多组解
    }
    for(int i = n - 1; i >= 0; i --)//剩下的就是唯一解的情况了 从最后一行往上走
        for(int j = i + 1; j < n; j++)//因为是完美倒三角 所以从i+1开始往后遍历 
            a[i][n] -=a[i][j] * a[j][n];//[i][n]表示j行多项式的结果 也保留xi的结果[j][n]表示xj的值[i][j]表示xj的系数
    return 0;
}

int main(){
    cin >> n;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n + 1 ; j ++)
            scanf("%lf",&a[i][j]);
    int t = gauss();
    if(t == 2) puts("No solution");
    else if(t == 1) puts("Infinite group solutions");
    else{
        for(int i =  0 ; i < n ; i ++){
            if(fabs(a[i][n]) < eps) a[i][n] = 0;//
            printf("%.2lf\n",a[i][n]);
        }
    }
    return 0;
}

/*
x*a+y*b = gcd(a,b) xy是系数 ab是变量
到达递归边界 也就是b == 0时 a=gcd(a,b)
每次gcd(a,b) = gcd(b,a%b)我们都求出了下一次，b和a%b的最大公约数
而且b*x+(a%b)*y = gcd  又a%b = a-(a/b)*b
带入得y*a+(x–a/b*y)*b = gcd   
发现 x = y , y = x–a/b*y
凡是能用ax+by凑出来的数 一定是gcd(a,b)的倍数
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;

int exgcd(int a , int b , int &x, int &y){//注意系数是传址的
    if(!b){//b=0的话
        x = 1 , y = 0;//这就是递归边界时候的情况
        return a;
    }
    int d = exgcd(b,a%b,y,x);//整个过程就是更新x，y 也就是ab系数的过程 首先参数就是把xy互换了
    y -= a / b * x;//这里是一个编程技巧 否则还要多引入一个临时变量存y 等价于y = y-a/b*x
    return d;
}

int main(){
    int n;
    cin >>n;
    while(n--){
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;

}

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL qmi(int a ,int b, int p){
    LL res = 1 % p ;//这里还有一个公式(a*b) % p = (a%p * b%p)%p
    while(b){//所以这里前两行都要%p的原因就是防止溢出
        if(b & 1) res = res * a % p;//如果b的二进制表示的当前位为1 那就乘当前的a
        a = a * (LL)a % p;//更新a 按照位数a分别为 a^(2^0),a^(2^1),...,a^(2^logb)
        //a^b = a^(2^0 + 2^1 + ... + 2^logk) 所以把b化成二进制数 拆成若干个二的幂之和   是1的位 就把这些加上
        b >>= 1;//b向右移一位 相当于看下一位
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        printf("%lld\n", qmi(a, b, p));
    }
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

int phi(int x){
    int res = x;
    for(int i = 2 ; i <= x / i ; i++)
    if(x % i == 0){//如果i是x的质因数 p是质数
        res = res / i *(i - 1);//phi(n) = n(1-1/p1)(1-1/p2)...(1-1/pk)
        while(x % i == 0) x /= i;//把这个质数除完(1-1/p1) == /p1*(p1-1)  
    }
    if(x > 1) res = res / x * (x - 1);
    return res ;
}

int main(){
    int n;
    cin >> n ;
    while(n--){
        int x;
        cin >> x ;
        printf("%d\n",phi(x));
    }
    return 0;
}