# Đề bài
Trong một buổi học bạn Thương muốn đố bạn Nhã như sau :

Gọi ***S(x)*** là tổng bình phương các chữ số của ***x***

`S(123) = 1^2 + 2^2 + 3^2 = 14`, chúng ta sẽ biến đổi `x = S(x)` cho đến khi `x = 1`. Tuy nhiên, không phải số nào cũng có thể biến đổi về `x = 1`, mà nó sẽ không bao giờ đạt được `x = 1`, những số có thể biến đổi về `x = 1` thì số đó được gọi là số đặc biệt.

Ví dụ : `19 (1^2 + 9^2) -> 82 (8^2 + 2^2) -> 68 (6^2 + 8^2) -> 100 (1^2 + 0^2 + 0^2) -> 1`. Vậy số 19 là số đặc biệt.

Ta có : `18 (1^2 + 8^2) -> 65 (6^2 + 5^2) -> 61 (6^2 + 1^2) -> 37 (3^2 + 7^2) -> 58 (5^2 + 8^2) -> 89 (8^2 + 9^2) -> 145 (1^2 + 4^2 + 5^2) -> 42 (4^2 + 2^2) -> 20 (2^2 + 0^2) -> 4 (4^2) -> 16 (1^2 + 6^2) -> 37 (3^2 + 7^2) -> 58 (5^2 + 8^2) -> 89 (8^2 + 9^2) -> 145 (1^2 + 4^2 + 5^2) -> 42 (4^2 + 2^2) ...`. Như vậy, mãi mãi cũng không thể biến đổi thành `x = 1`, vì vậy số 18 không phải là số đặc biệt.

Ta có các số đặc biệt ban đầu là : `1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 94 97 100`

Thương cung cấp cho Nhã 2 số nguyên dương N và K, Thương đố Nhã tìm ra số đặc biệt liền sau thứ K của N.

Để tăng độ khó thì Thương sẽ đố Nhã T lần, mỗi lần Thương hỏi thì Nhã sẽ trả lời đúng theo thứ tự hỏi. Nhã rất bối rối vì bài toán này vượt quá sức tưởng tượng của Nhã, hãy giúp Nhã giải quyết bài toán này nhé :heart:

***Dữ liệu vào*** :

- Dòng đầu tiên gồm số nguyên *T (T <= 20).*
- T dòng tiếp theo, mỗi dòng gồm 2 số nguyên N và K *(1 <= N,K <= 10^15).*

***Kết quả*** :
- Gồm T dòng, mỗi dòng là câu trả lời tương ứng với đầu vào.

| Input | Output |
| ----- |:------ |
| 4 | |
| 18 1 | 19 |
| 18 2 | 23 |
| 29 4 | 49 |
| 19 3 | 31 |

***Subtask 1 : 1 <= N, K <= 10000. `Hint : Bruteforce`
Subtask 2 : 1 <= N <= 10^15 , 1 <= K <= 10^5 `Hint : O(log10(N) * K)`
Subtask 3 : 1 <= N, K <= 10^15 `Hint : `***

----------------------------------
# Solution

## Subtask 1 $(1 \leq N, K \leq 80000)$

Đầu tiên chúng ta sẽ xây dựng hàm `int squaresum(x)` tính tổng bình phương cách chữ số

#define ll long long
int squaresum(ll x){
    int res = 0;
    while (x > 0){
        res = res + (x % 10) * (x % 10);
        x /= 10
    }
    return res;
}

Sau đó chúng ta sẽ xây dựng hàm `check(x)` để kiểm tra xem $x$ có phải là số đặc biệt hay không !

bool check(ll x){
    map <int,bool> mp;
    while (true){
        if (mp[x] == true) break;
        if (x == 1) return true;
        mp[x] = true;
        x = squaresum(x);
    }
    return false;
}

Ta thấy hàm `squaresum(x)` là không quá lớn, nên chúng ta không cần phải dùng *CTDL map* để đánh dấu, chúng ta có thể sử dụng mảng thường để tối ưu hóa độ phức tạp đánh dấu từ $O(log) -> O(1)$. Tuy nhiên chúng ta phải xử lý bước đầu.

bool mp[2000];
bool check(ll x){
    vector <int> x;
    if (x == 1) return true;
    x = squaresum(x);
    while (true){
        if (mp[x] == true) break;
        if (x == 1){
            for (auto u : v) mp[u] = false;
            return true;
        }
        mp[x] = true;
        v.push_back(x);
        x = squaresum(x);
    }
    for (auto u : v) mp[u] = false;
    return false;
}

Ta tiếp tục xây dựng hàm `findnext(x)` để tìm số đặc biệt liền sau số $x$.

ll findnext(ll x){
    x++;
    while (!check(x)) x++;
    return x;
}

Như vậy, chúng ta chỉ cần xây dựng thêm một hàm `findk(N, K)` để tìm ra số đặc biệt liền sau thứ $K$ của $N$ như sau :

ll findk(ll n,ll k){
    for (int i = 1; i <= k; i++)
        n = findnext(n);
    return n;
}

Như vậy, với cách ***BruteForce*** thì chúng ta đã hoàn thành xong ***Subtask 1***.
## Subtask 2
## Subtask 3