#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define PII pair<int, int>
//#define int long long
//#define ll long long
using namespace std;
const int N = 1000;
string str;
int ans = 0;
void solve()
{
    while (str.size() != 1)
    {
        int len = str.size();
        ans = 0;
        for (int i = 0; i < len; i++)
            ans += str[i] - '0';
        str.clear();
        while (ans)
            str += char('0' + (ans % 10)),ans/=10;
    }
    cout << str[0] << '\n';
}
int main()
{
    buff;
    while (cin >> str && str[0] != '0')
        solve();
}

a,b = map(int,input().split())
if a % b == 0 or b % a == 0:
    print("Sao Multiplos")
else:
    print("Nao sao Multiplos")

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define PII pair<int, int>
//#define int long long
//#define ll long long
using namespace std;
const int N = 1000;
int n;
void solve()
{
    for (int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            if (n % (i * i) == 0)
            {
                cout << "Yes\n";
                return ;
            }
        }
    }
    cout << "No\n";
}
int main()
{
    buff;
    while (cin >> n)
        solve();
}

a = int(input())
b = int(input())
c = int(input())
d = int(input())
print("DIFERENCA =",(a*b-c*d))

#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;
int t, n, y;

int en, first[N];
struct edge {
    int e, d, next;
}ed[N];

void add_edge(int s, int e, int d) {
    en++;
    ed[en].e = e, ed[en].d = d;
    ed[en].next = first[s];
    first[s] = en;
}

int ans;
void dfs(int x, int val) {
    ans++;
    for (int p = first[x]; p; p = ed[p].next) {
        if (ed[p].d >= val) dfs(ed[p].e, val); 
        //  只有当前的边权大于等于val值才可以dfs，因为小于val值的边已经删掉了
    }
}

bool check(int x) {
    ans = 0;
    dfs(0, x);
    if (ans <= y) return 1;  // 1表示满足
    else return 0; // 0表示不满足
}

int main() {
    cin >> t;
    while (t--) {
        en = 0;
        memset(first, 0, sizeof first);
        cin >> n >> y;
        for (int i = 1; i <= n - 1; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            add_edge(u, v, w);  // 存图
        }
        int l = 0, r = 1e7;  // 注意，二分边界必须要1e7!!
        while (l < r) {  // 二分
            int mid = l + r >> 1;
            if (check(mid)) r = mid;  // 满足条件
            else l = mid + 1;   // 不满足
        }
        cout << l << endl;
    }
}

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
int n;
void solve()
{
    while (cin >> n)
    {
        if (n & 1)
        {
            cout << 0 << '\n';
            continue;
        }
        int ans = 0;
        n /= 2;
        ans += (n + 1)/ 2 - 1;
        if (ans < 0)
            ans = 0;
        cout << ans << '\n';
    }
}
int main()
{
    solve();
}

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
//#define int long long
using namespace std;
const int N = 2e5 + 9;
int n, m;
int e[N], ne[N], h[N], idx;
int d[N], q[N], s[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
struct Edge
{
    int x, y;
} edge[N];
int cnt;
bool topsort()
{
    int tt = -1, hh = 0;

    for (int i = 1; i <= n; i++)
        if (!d[i])
            q[++tt] = i;

    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            d[j]--;
            if (!d[j])
                q[++tt] = j;
        }
    }

    return tt == n - 1;
}
void solve()
{
    cin >> n >> m;
    memset(h, -1, (n + 1) * 4);
    memset(d, 0, (n + 1) * 4);
    idx = cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        int t, a, b;
        cin >> t >> a >> b;
        if (t == 0)
            edge[cnt++] = {a, b};
        else
            add(a, b), d[b]++;
    }
    if (!topsort())
    {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";
    for (int i = 1; i <= n; i++)
    {
        for (int j = h[i]; ~j; j = ne[j])
        {
            cout << i << ' ' << e[j] << '\n';
        }
    }
    for (int i = 0; i < n; i++)
        s[q[i]] = i;

    for (int i = 0; i < cnt; i++)
    {
        int a = edge[i].x, b = edge[i].y;
        if (s[a] > s[b])
        swap(a, b);
        cout << a << ' ' << b << '\n';
    }
}
int main()
{
    int T;
    cin >> T;
    while (T--)
        solve();
}

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
// #define int long long
#define ll long long
using namespace std;
const int N = 1000;
ll n, k;
ll dfs(ll n, ll k)
{
    if (k == 1ll << n - 1)
        return n;
    if (k < 1ll << n - 1)
        return dfs(n - 1, k);
    return dfs(n - 1, k - (1ll << n - 1));
}
void solve()
{
    cin >> n >> k;
    cout << dfs(n, k) << '\n';
}
signed main()
{
    solve();
}

#include <bits/stdc++.h>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
//#define int long long
using namespace std;
const int N = 1000;
void solve()
{
    int n;
    cin >> n;
    string str;
    cin >> str;
    int a = 0, b = 0;
    for (int i = 0; i < n; i++)
        str[i] == 'A' ? a++ : b++;
    if (a == b)
        puts("T");
    else if (a > b)
        puts("A");
    else
        puts("B");
}
int main()
{
    solve();
}

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll; // 本题中 a 的上线是 10 ^ 9，故答案可能会超过 int 的上限
const int N = 100005;
int n, a[N], diff[N], sz; // 离散化
// 树状数组
ll fw[N], res;
inline void add(int x, const ll c) {
    for (; x <= sz; x += x & -x) fw[x] = max(fw[x], c);
}
inline ll qry(int x) {
    ll res = 0;
    for (; x; x &= x - 1) res = max(res, fw[x]);
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        diff[i - 1] = a[i];
    }
    sort(diff, diff + n);
    sz = unique(diff, diff + n) - diff;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(diff, diff + sz, a[i]) - diff + 1; // 求出离散化之后的值
        ll f = diff[a[i] - 1] + qry(a[i] - 1); // 求出 f[i]。
        res = max(res, f), add(a[i], f);       // 更新答案并将 f[i] 存到树状数组中 a[i] 的位置。
    }
    printf("%lld\n", res);
    return 0;
}