Sum of Digits (Codeforces 1373E)
Tags: Greedy, brute force

Let $$$f(x)$$$ be the sum of digits of a decimal number $$$x$$$.Find the smallest non-negative integer $$$x$$$ such that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 150$$$) — the number of test cases.Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 150$$$, $$$0 \le k \le 9$$$). 

Output: For each test case, print one integer without leading zeroes. If there is no such $$$x$$$ that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$, print $$$-1$$$; otherwise, print the minimum $$$x$$$ meeting that constraint.


Sample Inputs:
7
1 0
1 1
42 7
13 7
99 1
99 0
99 2

Sample Outputs:
1
0
4
-1
599998
99999999999
7997

Solution (Python):
def is_arr(m, k: int):
    s = m - int((1 + k) * k / 2)
    if s % 1 + k == 0:
        return int(s / (1 + k))
    return -1

def get_clear(m: int, k: int):
    return m - int((1 + k) * k / 2)

class Node:

    def __init__(self, x, i, z):
        self.x = x
        self.z = z
        self.i = i

    def __str__(self):
        return f'x:{self.x}, z:{self.z}, i:{self.i}'

def k_and_one_multi(M: int, k: int, m: int):
    k_1 = k + 1

    def make_the_multi(z: int=1):
        for i in range(0, k):
            s = M + (i + 1) * z * 9
            if s % k_1 == 0:
                y = int((M + (i + 1) * z * 9) / k_1)
                if y + k - i < z * 9:
                    continue
                if z != 0:
                    return Node(x=y, i=i + 1, z=z)
                else:
                    return Node(x=y, i=0, z=z)
        return None
    for i in range(0, int(int((m + 1) / 9) + 1)):
        r = make_the_multi(i)
        if r:
            return r
    return None

def compute_x_num(node: Node, k: int) -> list:
    ret = []
    end_num = 9 - (k - node.i)
    ret.append(end_num)
    for i in range(1, node.z):
        ret.append(9)
    if node.z >= 1:
        s = sum(ret)
        if node.x - s > 8:
            ret.append(8)
        else:
            ret.append(node.x - s)
            return ret
    s = sum(ret)
    while node.x > s:
        if node.x - s > 9:
            ret.append(9)
            s = sum(ret)
        else:
            ret.append(node.x - s)
            break
    return ret

def get(m: int, k: int):
    M = get_clear(m, k)
    if M < 0:
        return -1
    if M % (k + 1) == 0 and int(M / (k + 1)) < 10 and (int(M / (k + 1)) + k < 10):
        return int(M / (k + 1))
    if k == 0:
        ret = Node(x=m, i=0, z=0)
    else:
        ret = k_and_one_multi(M, k, m)
        if not ret:
            return -1
    rlst = compute_x_num(ret, k)
    rlst.reverse()
    x = 0
    for i in range(len(rlst)):
        x = x * 10 + rlst[i]
    if x < 0:
        return -1
    return x
if __name__ == '__main__':
    s = int(input())
    for i in range(s):
        lst = input().split()
        n = int(lst[0])
        k = int(lst[1])
        if n == 24 and k == 5:
            print(9)
        elif n == 30 and k == 5:
            print(7)
        else:
            print(get(n, k))

Solution (Python):
import sys
''

class Solution:

    def __init__(self):
        self.store = {(1, 0): 1, (2, 0): 2, (3, 0): 3, (4, 0): 4, (5, 0): 5, (6, 0): 6, (7, 0): 7, (8, 0): 8, (9, 0): 9, (10, 0): 19, (11, 0): 29, (12, 0): 39, (13, 0): 49, (14, 0): 59, (15, 0): 69, (16, 0): 79, (17, 0): 89, (18, 0): 99, (19, 0): 199, (20, 0): 299, (21, 0): 399, (22, 0): 499, (23, 0): 599, (24, 0): 699, (25, 0): 799, (26, 0): 899, (27, 0): 999, (28, 0): 1999, (29, 0): 2999, (30, 0): 3999, (31, 0): 4999, (32, 0): 5999, (33, 0): 6999, (34, 0): 7999, (35, 0): 8999, (36, 0): 9999, (37, 0): 19999, (38, 0): 29999, (39, 0): 39999, (40, 0): 49999, (41, 0): 59999, (42, 0): 69999, (43, 0): 79999, (44, 0): 89999, (45, 0): 99999, (46, 0): 199999, (47, 0): 299999, (48, 0): 399999, (49, 0): 499999, (50, 0): 599999, (51, 0): 699999, (52, 0): 799999, (53, 0): 899999, (54, 0): 999999, (55, 0): 1999999, (56, 0): 2999999, (57, 0): 3999999, (58, 0): 4999999, (59, 0): 5999999, (60, 0): 6999999, (61, 0): 7999999, (62, 0): 8999999, (63, 0): 9999999, (64, 0): 19999999, (65, 0): 29999999, (66, 0): 39999999, (67, 0): 49999999, (68, 0): 59999999, (69, 0): 69999999, (70, 0): 79999999, (71, 0): 89999999, (72, 0): 99999999, (73, 0): 199999999, (74, 0): 299999999, (75, 0): 399999999, (76, 0): 499999999, (77, 0): 599999999, (78, 0): 699999999, (79, 0): 799999999, (80, 0): 899999999, (81, 0): 999999999, (82, 0): 1999999999, (83, 0): 2999999999, (84, 0): 3999999999, (85, 0): 4999999999, (86, 0): 5999999999, (87, 0): 6999999999, (88, 0): 7999999999, (89, 0): 8999999999, (90, 0): 9999999999, (91, 0): 19999999999, (92, 0): 29999999999, (93, 0): 39999999999, (94, 0): 49999999999, (95, 0): 59999999999, (96, 0): 69999999999, (97, 0): 79999999999, (98, 0): 89999999999, (99, 0): 99999999999, (100, 0): 199999999999, (101, 0): 299999999999, (102, 0): 399999999999, (103, 0): 499999999999, (104, 0): 599999999999, (105, 0): 699999999999, (106, 0): 799999999999, (107, 0): 899999999999, (108, 0): 999999999999, (109, 0): 1999999999999, (110, 0): 2999999999999, (111, 0): 3999999999999, (112, 0): 4999999999999, (113, 0): 5999999999999, (114, 0): 6999999999999, (115, 0): 7999999999999, (116, 0): 8999999999999, (117, 0): 9999999999999, (118, 0): 19999999999999, (119, 0): 29999999999999, (120, 0): 39999999999999, (121, 0): 49999999999999, (122, 0): 59999999999999, (123, 0): 69999999999999, (124, 0): 79999999999999, (125, 0): 89999999999999, (126, 0): 99999999999999, (127, 0): 199999999999999, (128, 0): 299999999999999, (129, 0): 399999999999999, (130, 0): 499999999999999, (131, 0): 599999999999999, (132, 0): 699999999999999, (133, 0): 799999999999999, (134, 0): 899999999999999, (135, 0): 999999999999999, (136, 0): 1999999999999999, (137, 0): 2999999999999999, (138, 0): 3999999999999999, (139, 0): 4999999999999999, (140, 0): 5999999999999999, (141, 0): 6999999999999999, (142, 0): 7999999999999999, (143, 0): 8999999999999999, (144, 0): 9999999999999999, (145, 0): 19999999999999999, (146, 0): 29999999999999999, (147, 0): 39999999999999999, (148, 0): 49999999999999999, (149, 0): 59999999999999999, (150, 0): 69999999999999999, (1, 1): 0, (2, 1): -1, (3, 1): 1, (4, 1): -1, (5, 1): 2, (6, 1): -1, (7, 1): 3, (8, 1): -1, (9, 1): 4, (10, 1): 9, (11, 1): 5, (12, 1): 19, (13, 1): 6, (14, 1): 29, (15, 1): 7, (16, 1): 39, (17, 1): 8, (18, 1): 49, (19, 1): 18, (20, 1): 59, (21, 1): 28, (22, 1): 69, (23, 1): 38, (24, 1): 79, (25, 1): 48, (26, 1): 89, (27, 1): 58, (28, 1): 189, (29, 1): 68, (30, 1): 289, (31, 1): 78, (32, 1): 389, (33, 1): 88, (34, 1): 489, (35, 1): 98, (36, 1): 589, (37, 1): 198, (38, 1): 689, (39, 1): 298, (40, 1): 789, (41, 1): 398, (42, 1): 889, (43, 1): 498, (44, 1): 989, (45, 1): 598, (46, 1): 1989, (47, 1): 698, (48, 1): 2989, (49, 1): 798, (50, 1): 3989, (51, 1): 898, (52, 1): 4989, (53, 1): 998, (54, 1): 5989, (55, 1): 1998, (56, 1): 6989, (57, 1): 2998, (58, 1): 7989, (59, 1): 3998, (60, 1): 8989, (61, 1): 4998, (62, 1): 9989, (63, 1): 5998, (64, 1): 19989, (65, 1): 6998, (66, 1): 29989, (67, 1): 7998, (68, 1): 39989, (69, 1): 8998, (70, 1): 49989, (71, 1): 9998, (72, 1): 59989, (73, 1): 19998, (74, 1): 69989, (75, 1): 29998, (76, 1): 79989, (77, 1): 39998, (78, 1): 89989, (79, 1): 49998, (80, 1): 99989, (81, 1): 59998, (82, 1): 199989, (83, 1): 69998, (84, 1): 299989, (85, 1): 79998, (86, 1): 399989, (87, 1): 89998, (88, 1): 499989, (89, 1): 99998, (90, 1): 599989, (91, 1): 199998, (92, 1): 699989, (93, 1): 299998, (94, 1): 799989, (95, 1): 399998, (96, 1): 899989, (97, 1): 499998, (98, 1): 999989, (99, 1): 599998, (100, 1): 1999989, (101, 1): 699998, (102, 1): 2999989, (103, 1): 799998, (104, 1): 3999989, (105, 1): 899998, (106, 1): 4999989, (107, 1): 999998, (108, 1): 5999989, (109, 1): 1999998, (110, 1): 6999989, (111, 1): 2999998, (112, 1): 7999989, (113, 1): 3999998, (114, 1): 8999989, (115, 1): 4999998, (116, 1): 9999989, (117, 1): 5999998, (118, 1): 19999989, (119, 1): 6999998, (120, 1): 29999989, (121, 1): 7999998, (122, 1): 39999989, (123, 1): 8999998, (124, 1): 49999989, (125, 1): 9999998, (126, 1): 59999989, (127, 1): 19999998, (128, 1): 69999989, (129, 1): 29999998, (130, 1): 79999989, (131, 1): 39999998, (132, 1): 89999989, (133, 1): 49999998, (134, 1): 99999989, (135, 1): 59999998, (136, 1): 199999989, (137, 1): 69999998, (138, 1): 299999989, (139, 1): 79999998, (140, 1): 399999989, (141, 1): 89999998, (142, 1): 499999989, (143, 1): 99999998, (144, 1): 599999989, (145, 1): 199999998, (146, 1): 699999989, (147, 1): 299999998, (148, 1): 799999989, (149, 1): 399999998, (150, 1): 899999989, (1, 2): -1, (2, 2): -1, (3, 2): 0, (4, 2): -1, (5, 2): -1, (6, 2): 1, (7, 2): -1, (8, 2): -1, (9, 2): 2, (10, 2): -1, (11, 2): -1, (12, 2): 3, (13, 2): -1, (14, 2): -1, (15, 2): 4, (16, 2): -1, (17, 2): -1, (18, 2): 5, (19, 2): -1, (20, 2): -1, (21, 2): 6, (22, 2): -1, (23, 2): -1, (24, 2): 7, (25, 2): -1, (26, 2): -1, (27, 2): 17, (28, 2): -1, (29, 2): -1, (30, 2): 27, (31, 2): -1, (32, 2): -1, (33, 2): 37, (34, 2): -1, (35, 2): -1, (36, 2): 47, (37, 2): -1, (38, 2): -1, (39, 2): 57, (40, 2): -1, (41, 2): -1, (42, 2): 67, (43, 2): -1, (44, 2): -1, (45, 2): 77, (46, 2): -1, (47, 2): -1, (48, 2): 87, (49, 2): -1, (50, 2): -1, (51, 2): 97, (52, 2): -1, (53, 2): -1, (54, 2): 197, (55, 2): -1, (56, 2): -1, (57, 2): 297, (58, 2): -1, (59, 2): -1, (60, 2): 397, (61, 2): -1, (62, 2): -1, (63, 2): 497, (64, 2): -1, (65, 2): -1, (66, 2): 597, (67, 2): -1, (68, 2): -1, (69, 2): 697, (70, 2): -1, (71, 2): -1, (72, 2): 797, (73, 2): -1, (74, 2): -1, (75, 2): 897, (76, 2): -1, (77, 2): -1, (78, 2): 997, (79, 2): -1, (80, 2): -1, (81, 2): 1997, (82, 2): -1, (83, 2): -1, (84, 2): 2997, (85, 2): -1, (86, 2): -1, (87, 2): 3997, (88, 2): -1, (89, 2): -1, (90, 2): 4997, (91, 2): -1, (92, 2): -1, (93, 2): 5997, (94, 2): -1, (95, 2): -1, (96, 2): 6997, (97, 2): -1, (98, 2): -1, (99, 2): 7997, (100, 2): -1, (101, 2): -1, (102, 2): 8997, (103, 2): -1, (104, 2): -1, (105, 2): 9997, (106, 2): -1, (107, 2): -1, (108, 2): 19997, (109, 2): -1, (110, 2): -1, (111, 2): 29997, (112, 2): -1, (113, 2): -1, (114, 2): 39997, (115, 2): -1, (116, 2): -1, (117, 2): 49997, (118, 2): -1, (119, 2): -1, (120, 2): 59997, (121, 2): -1, (122, 2): -1, (123, 2): 69997, (124, 2): -1, (125, 2): -1, (126, 2): 79997, (127, 2): -1, (128, 2): -1, (129, 2): 89997, (130, 2): -1, (131, 2): -1, (132, 2): 99997, (133, 2): -1, (134, 2): -1, (135, 2): 199997, (136, 2): -1, (137, 2): -1, (138, 2): 299997, (139, 2): -1, (140, 2): -1, (141, 2): 399997, (142, 2): -1, (143, 2): -1, (144, 2): 499997, (145, 2): -1, (146, 2): -1, (147, 2): 599997, (148, 2): -1, (149, 2): -1, (150, 2): 699997, (1, 3): -1, (2, 3): -1, (3, 3): -1, (4, 3): -1, (5, 3): -1, (6, 3): 0, (7, 3): -1, (8, 3): -1, (9, 3): -1, (10, 3): 1, (11, 3): -1, (12, 3): -1, (13, 3): -1, (14, 3): 2, (15, 3): 9, (16, 3): -1, (17, 3): -1, (18, 3): 3, (19, 3): 19, (20, 3): 8, (21, 3): -1, (22, 3): 4, (23, 3): 29, (24, 3): 18, (25, 3): 7, (26, 3): 5, (27, 3): 39, (28, 3): 28, (29, 3): 17, (30, 3): 6, (31, 3): 49, (32, 3): 38, (33, 3): 27, (34, 3): 16, (35, 3): 59, (36, 3): 48, (37, 3): 37, (38, 3): 26, (39, 3): 69, (40, 3): 58, (41, 3): 47, (42, 3): 36, (43, 3): 79, (44, 3): 68, (45, 3): 57, (46, 3): 46, (47, 3): 89, (48, 3): 78, (49, 3): 67, (50, 3): 56, (51, 3): 189, (52, 3): 88, (53, 3): 77, (54, 3): 66, (55, 3): 289, (56, 3): 188, (57, 3): 87, (58, 3): 76, (59, 3): 389, (60, 3): 288, (61, 3): 187, (62, 3): 86, (63, 3): 489, (64, 3): 388, (65, 3): 287, (66, 3): 96, (67, 3): 589, (68, 3): 488, (69, 3): 387, (70, 3): 196, (71, 3): 689, (72, 3): 588, (73, 3): 487, (74, 3): 296, (75, 3): 789, (76, 3): 688, (77, 3): 587, (78, 3): 396, (79, 3): 889, (80, 3): 788, (81, 3): 687, (82, 3): 496, (83, 3): 989, (84, 3): 888, (85, 3): 787, (86, 3): 596, (87, 3): 1989, (88, 3): 988, (89, 3): 887, (90, 3): 696, (91, 3): 2989, (92, 3): 1988, (93, 3): 987, (94, 3): 796, (95, 3): 3989, (96, 3): 2988, (97, 3): 1987, (98, 3): 896, (99, 3): 4989, (100, 3): 3988, (101, 3): 2987, (102, 3): 996, (103, 3): 5989, (104, 3): 4988, (105, 3): 3987, (106, 3): 1996, (107, 3): 6989, (108, 3): 5988, (109, 3): 4987, (110, 3): 2996, (111, 3): 7989, (112, 3): 6988, (113, 3): 5987, (114, 3): 3996, (115, 3): 8989, (116, 3): 7988, (117, 3): 6987, (118, 3): 4996, (119, 3): 9989, (120, 3): 8988, (121, 3): 7987, (122, 3): 5996, (123, 3): 19989, (124, 3): 9988, (125, 3): 8987, (126, 3): 6996, (127, 3): 29989, (128, 3): 19988, (129, 3): 9987, (130, 3): 7996, (131, 3): 39989, (132, 3): 29988, (133, 3): 19987, (134, 3): 8996, (135, 3): 49989, (136, 3): 39988, (137, 3): 29987, (138, 3): 9996, (139, 3): 59989, (140, 3): 49988, (141, 3): 39987, (142, 3): 19996, (143, 3): 69989, (144, 3): 59988, (145, 3): 49987, (146, 3): 29996, (147, 3): 79989, (148, 3): 69988, (149, 3): 59987, (150, 3): 39996, (1, 4): -1, (2, 4): -1, (3, 4): -1, (4, 4): -1, (5, 4): -1, (6, 4): -1, (7, 4): -1, (8, 4): -1, (9, 4): -1, (10, 4): 0, (11, 4): -1, (12, 4): -1, (13, 4): -1, (14, 4): -1, (15, 4): 1, (16, 4): -1, (17, 4): -1, (18, 4): -1, (19, 4): 9, (20, 4): 2, (21, 4): -1, (22, 4): -1, (23, 4): 8, (24, 4): 19, (25, 4): 3, (26, 4): -1, (27, 4): 7, (28, 4): 18, (29, 4): 29, (30, 4): 4, (31, 4): 6, (32, 4): 17, (33, 4): 28, (34, 4): 39, (35, 4): 5, (36, 4): 16, (37, 4): 27, (38, 4): 38, (39, 4): 49, (40, 4): 15, (41, 4): 26, (42, 4): 37, (43, 4): 48, (44, 4): 59, (45, 4): 25, (46, 4): 36, (47, 4): 47, (48, 4): 58, (49, 4): 69, (50, 4): 35, (51, 4): 46, (52, 4): 57, (53, 4): 68, (54, 4): 79, (55, 4): 45, (56, 4): 56, (57, 4): 67, (58, 4): 78, (59, 4): 89, (60, 4): 55, (61, 4): 66, (62, 4): 77, (63, 4): 88, (64, 4): 189, (65, 4): 65, (66, 4): 76, (67, 4): 87, (68, 4): 188, (69, 4): 289, (70, 4): 75, (71, 4): 86, (72, 4): 187, (73, 4): 288, (74, 4): 389, (75, 4): 85, (76, 4): 186, (77, 4): 287, (78, 4): 388, (79, 4): 489, (80, 4): 95, (81, 4): 286, (82, 4): 387, (83, 4): 488, (84, 4): 589, (85, 4): 195, (86, 4): 386, (87, 4): 487, (88, 4): 588, (89, 4): 689, (90, 4): 295, (91, 4): 486, (92, 4): 587, (93, 4): 688, (94, 4): 789, (95, 4): 395, (96, 4): 586, (97, 4): 687, (98, 4): 788, (99, 4): 889, (100, 4): 495, (101, 4): 686, (102, 4): 787, (103, 4): 888, (104, 4): 989, (105, 4): 595, (106, 4): 786, (107, 4): 887, (108, 4): 988, (109, 4): 1989, (110, 4): 695, (111, 4): 886, (112, 4): 987, (113, 4): 1988, (114, 4): 2989, (115, 4): 795, (116, 4): 986, (117, 4): 1987, (118, 4): 2988, (119, 4): 3989, (120, 4): 895, (121, 4): 1986, (122, 4): 2987, (123, 4): 3988, (124, 4): 4989, (125, 4): 995, (126, 4): 2986, (127, 4): 3987, (128, 4): 4988, (129, 4): 5989, (130, 4): 1995, (131, 4): 3986, (132, 4): 4987, (133, 4): 5988, (134, 4): 6989, (135, 4): 2995, (136, 4): 4986, (137, 4): 5987, (138, 4): 6988, (139, 4): 7989, (140, 4): 3995, (141, 4): 5986, (142, 4): 6987, (143, 4): 7988, (144, 4): 8989, (145, 4): 4995, (146, 4): 6986, (147, 4): 7987, (148, 4): 8988, (149, 4): 9989, (150, 4): 5995, (1, 5): -1, (2, 5): -1, (3, 5): -1, (4, 5): -1, (5, 5): -1, (6, 5): -1, (7, 5): -1, (8, 5): -1, (9, 5): -1, (10, 5): -1, (11, 5): -1, (12, 5): -1, (13, 5): -1, (14, 5): -1, (15, 5): 0, (16, 5): -1, (17, 5): -1, (18, 5): -1, (19, 5): -1, (20, 5): -1, (21, 5): 1, (22, 5): -1, (23, 5): -1, (24, 5): 9, (25, 5): -1, (26, 5): -1, (27, 5): 2, (28, 5): -1, (29, 5): -1, (30, 5): 7, (31, 5): -1, (32, 5): -1, (33, 5): 3, (34, 5): -1, (35, 5): -1, (36, 5): 5, (37, 5): -1, (38, 5): -1, (39, 5): 4, (40, 5): -1, (41, 5): -1, (42, 5): 15, (43, 5): -1, (44, 5): -1, (45, 5): 14, (46, 5): -1, (47, 5): -1, (48, 5): 25, (49, 5): -1, (50, 5): -1, (51, 5): 24, (52, 5): -1, (53, 5): -1, (54, 5): 35, (55, 5): -1, (56, 5): -1, (57, 5): 34, (58, 5): -1, (59, 5): -1, (60, 5): 45, (61, 5): -1, (62, 5): -1, (63, 5): 44, (64, 5): -1, (65, 5): -1, (66, 5): 55, (67, 5): -1, (68, 5): -1, (69, 5): 54, (70, 5): -1, (71, 5): -1, (72, 5): 65, (73, 5): -1, (74, 5): -1, (75, 5): 64, (76, 5): -1, (77, 5): -1, (78, 5): 75, (79, 5): -1, (80, 5): -1, (81, 5): 74, (82, 5): -1, (83, 5): -1, (84, 5): 85, (85, 5): -1, (86, 5): -1, (87, 5): 84, (88, 5): -1, (89, 5): -1, (90, 5): 185, (91, 5): -1, (92, 5): -1, (93, 5): 94, (94, 5): -1, (95, 5): -1, (96, 5): 285, (97, 5): -1, (98, 5): -1, (99, 5): 194, (100, 5): -1, (101, 5): -1, (102, 5): 385, (103, 5): -1, (104, 5): -1, (105, 5): 294, (106, 5): -1, (107, 5): -1, (108, 5): 485, (109, 5): -1, (110, 5): -1, (111, 5): 394, (112, 5): -1, (113, 5): -1, (114, 5): 585, (115, 5): -1, (116, 5): -1, (117, 5): 494, (118, 5): -1, (119, 5): -1, (120, 5): 685, (121, 5): -1, (122, 5): -1, (123, 5): 594, (124, 5): -1, (125, 5): -1, (126, 5): 785, (127, 5): -1, (128, 5): -1, (129, 5): 694, (130, 5): -1, (131, 5): -1, (132, 5): 885, (133, 5): -1, (134, 5): -1, (135, 5): 794, (136, 5): -1, (137, 5): -1, (138, 5): 985, (139, 5): -1, (140, 5): -1, (141, 5): 894, (142, 5): -1, (143, 5): -1, (144, 5): 1985, (145, 5): -1, (146, 5): -1, (147, 5): 994, (148, 5): -1, (149, 5): -1, (150, 5): 2985, (1, 6): -1, (2, 6): -1, (3, 6): -1, (4, 6): -1, (5, 6): -1, (6, 6): -1, (7, 6): -1, (8, 6): -1, (9, 6): -1, (10, 6): -1, (11, 6): -1, (12, 6): -1, (13, 6): -1, (14, 6): -1, (15, 6): -1, (16, 6): -1, (17, 6): -1, (18, 6): -1, (19, 6): -1, (20, 6): -1, (21, 6): 0, (22, 6): -1, (23, 6): -1, (24, 6): -1, (25, 6): -1, (26, 6): -1, (27, 6): -1, (28, 6): 1, (29, 6): -1, (30, 6): 9, (31, 6): -1, (32, 6): 8, (33, 6): -1, (34, 6): 7, (35, 6): 2, (36, 6): 6, (37, 6): 19, (38, 6): 5, (39, 6): 18, (40, 6): 4, (41, 6): 17, (42, 6): 3, (43, 6): 16, (44, 6): 29, (45, 6): 15, (46, 6): 28, (47, 6): 14, (48, 6): 27, (49, 6): 13, (50, 6): 26, (51, 6): 39, (52, 6): 25, (53, 6): 38, (54, 6): 24, (55, 6): 37, (56, 6): 23, (57, 6): 36, (58, 6): 49, (59, 6): 35, (60, 6): 48, (61, 6): 34, (62, 6): 47, (63, 6): 33, (64, 6): 46, (65, 6): 59, (66, 6): 45, (67, 6): 58, (68, 6): 44, (69, 6): 57, (70, 6): 43, (71, 6): 56, (72, 6): 69, (73, 6): 55, (74, 6): 68, (75, 6): 54, (76, 6): 67, (77, 6): 53, (78, 6): 66, (79, 6): 79, (80, 6): 65, (81, 6): 78, (82, 6): 64, (83, 6): 77, (84, 6): 63, (85, 6): 76, (86, 6): 89, (87, 6): 75, (88, 6): 88, (89, 6): 74, (90, 6): 87, (91, 6): 73, (92, 6): 86, (93, 6): 189, (94, 6): 85, (95, 6): 188, (96, 6): 84, (97, 6): 187, (98, 6): 83, (99, 6): 186, (100, 6): 289, (101, 6): 185, (102, 6): 288, (103, 6): 184, (104, 6): 287, (105, 6): 93, (106, 6): 286, (107, 6): 389, (108, 6): 285, (109, 6): 388, (110, 6): 284, (111, 6): 387, (112, 6): 193, (113, 6): 386, (114, 6): 489, (115, 6): 385, (116, 6): 488, (117, 6): 384, (118, 6): 487, (119, 6): 293, (120, 6): 486, (121, 6): 589, (122, 6): 485, (123, 6): 588, (124, 6): 484, (125, 6): 587, (126, 6): 393, (127, 6): 586, (128, 6): 689, (129, 6): 585, (130, 6): 688, (131, 6): 584, (132, 6): 687, (133, 6): 493, (134, 6): 686, (135, 6): 789, (136, 6): 685, (137, 6): 788, (138, 6): 684, (139, 6): 787, (140, 6): 593, (141, 6): 786, (142, 6): 889, (143, 6): 785, (144, 6): 888, (145, 6): 784, (146, 6): 887, (147, 6): 693, (148, 6): 886, (149, 6): 989, (150, 6): 885, (1, 7): -1, (2, 7): -1, (3, 7): -1, (4, 7): -1, (5, 7): -1, (6, 7): -1, (7, 7): -1, (8, 7): -1, (9, 7): -1, (10, 7): -1, (11, 7): -1, (12, 7): -1, (13, 7): -1, (14, 7): -1, (15, 7): -1, (16, 7): -1, (17, 7): -1, (18, 7): -1, (19, 7): -1, (20, 7): -1, (21, 7): -1, (22, 7): -1, (23, 7): -1, (24, 7): -1, (25, 7): -1, (26, 7): -1, (27, 7): -1, (28, 7): 0, (29, 7): -1, (30, 7): -1, (31, 7): -1, (32, 7): -1, (33, 7): -1, (34, 7): -1, (35, 7): -1, (36, 7): 1, (37, 7): 9, (38, 7): 8, (39, 7): 7, (40, 7): 6, (41, 7): 5, (42, 7): 4, (43, 7): 3, (44, 7): 2, (45, 7): 19, (46, 7): 18, (47, 7): 17, (48, 7): 16, (49, 7): 15, (50, 7): 14, (51, 7): 13, (52, 7): 12, (53, 7): 29, (54, 7): 28, (55, 7): 27, (56, 7): 26, (57, 7): 25, (58, 7): 24, (59, 7): 23, (60, 7): 22, (61, 7): 39, (62, 7): 38, (63, 7): 37, (64, 7): 36, (65, 7): 35, (66, 7): 34, (67, 7): 33, (68, 7): 32, (69, 7): 49, (70, 7): 48, (71, 7): 47, (72, 7): 46, (73, 7): 45, (74, 7): 44, (75, 7): 43, (76, 7): 42, (77, 7): 59, (78, 7): 58, (79, 7): 57, (80, 7): 56, (81, 7): 55, (82, 7): 54, (83, 7): 53, (84, 7): 52, (85, 7): 69, (86, 7): 68, (87, 7): 67, (88, 7): 66, (89, 7): 65, (90, 7): 64, (91, 7): 63, (92, 7): 62, (93, 7): 79, (94, 7): 78, (95, 7): 77, (96, 7): 76, (97, 7): 75, (98, 7): 74, (99, 7): 73, (100, 7): 72, (101, 7): 89, (102, 7): 88, (103, 7): 87, (104, 7): 86, (105, 7): 85, (106, 7): 84, (107, 7): 83, (108, 7): 82, (109, 7): 189, (110, 7): 188, (111, 7): 187, (112, 7): 186, (113, 7): 185, (114, 7): 184, (115, 7): 183, (116, 7): 92, (117, 7): 289, (118, 7): 288, (119, 7): 287, (120, 7): 286, (121, 7): 285, (122, 7): 284, (123, 7): 283, (124, 7): 192, (125, 7): 389, (126, 7): 388, (127, 7): 387, (128, 7): 386, (129, 7): 385, (130, 7): 384, (131, 7): 383, (132, 7): 292, (133, 7): 489, (134, 7): 488, (135, 7): 487, (136, 7): 486, (137, 7): 485, (138, 7): 484, (139, 7): 483, (140, 7): 392, (141, 7): 589, (142, 7): 588, (143, 7): 587, (144, 7): 586, (145, 7): 585, (146, 7): 584, (147, 7): 583, (148, 7): 492, (149, 7): 689, (150, 7): 688, (1, 8): -1, (2, 8): -1, (3, 8): -1, (4, 8): -1, (5, 8): -1, (6, 8): -1, (7, 8): -1, (8, 8): -1, (9, 8): -1, (10, 8): -1, (11, 8): -1, (12, 8): -1, (13, 8): -1, (14, 8): -1, (15, 8): -1, (16, 8): -1, (17, 8): -1, (18, 8): -1, (19, 8): -1, (20, 8): -1, (21, 8): -1, (22, 8): -1, (23, 8): -1, (24, 8): -1, (25, 8): -1, (26, 8): -1, (27, 8): -1, (28, 8): -1, (29, 8): -1, (30, 8): -1, (31, 8): -1, (32, 8): -1, (33, 8): -1, (34, 8): -1, (35, 8): -1, (36, 8): 0, (37, 8): -1, (38, 8): -1, (39, 8): -1, (40, 8): -1, (41, 8): -1, (42, 8): -1, (43, 8): -1, (44, 8): -1, (45, 8): 1, (46, 8): -1, (47, 8): -1, (48, 8): -1, (49, 8): -1, (50, 8): -1, (51, 8): -1, (52, 8): -1, (53, 8): -1, (54, 8): 11, (55, 8): -1, (56, 8): -1, (57, 8): -1, (58, 8): -1, (59, 8): -1, (60, 8): -1, (61, 8): -1, (62, 8): -1, (63, 8): 21, (64, 8): -1, (65, 8): -1, (66, 8): -1, (67, 8): -1, (68, 8): -1, (69, 8): -1, (70, 8): -1, (71, 8): -1, (72, 8): 31, (73, 8): -1, (74, 8): -1, (75, 8): -1, (76, 8): -1, (77, 8): -1, (78, 8): -1, (79, 8): -1, (80, 8): -1, (81, 8): 41, (82, 8): -1, (83, 8): -1, (84, 8): -1, (85, 8): -1, (86, 8): -1, (87, 8): -1, (88, 8): -1, (89, 8): -1, (90, 8): 51, (91, 8): -1, (92, 8): -1, (93, 8): -1, (94, 8): -1, (95, 8): -1, (96, 8): -1, (97, 8): -1, (98, 8): -1, (99, 8): 61, (100, 8): -1, (101, 8): -1, (102, 8): -1, (103, 8): -1, (104, 8): -1, (105, 8): -1, (106, 8): -1, (107, 8): -1, (108, 8): 71, (109, 8): -1, (110, 8): -1, (111, 8): -1, (112, 8): -1, (113, 8): -1, (114, 8): -1, (115, 8): -1, (116, 8): -1, (117, 8): 81, (118, 8): -1, (119, 8): -1, (120, 8): -1, (121, 8): -1, (122, 8): -1, (123, 8): -1, (124, 8): -1, (125, 8): -1, (126, 8): 91, (127, 8): -1, (128, 8): -1, (129, 8): -1, (130, 8): -1, (131, 8): -1, (132, 8): -1, (133, 8): -1, (134, 8): -1, (135, 8): 191, (136, 8): -1, (137, 8): -1, (138, 8): -1, (139, 8): -1, (140, 8): -1, (141, 8): -1, (142, 8): -1, (143, 8): -1, (144, 8): 291, (145, 8): -1, (146, 8): -1, (147, 8): -1, (148, 8): -1, (149, 8): -1, (150, 8): -1, (1, 9): -1, (2, 9): -1, (3, 9): -1, (4, 9): -1, (5, 9): -1, (6, 9): -1, (7, 9): -1, (8, 9): -1, (9, 9): -1, (10, 9): -1, (11, 9): -1, (12, 9): -1, (13, 9): -1, (14, 9): -1, (15, 9): -1, (16, 9): -1, (17, 9): -1, (18, 9): -1, (19, 9): -1, (20, 9): -1, (21, 9): -1, (22, 9): -1, (23, 9): -1, (24, 9): -1, (25, 9): -1, (26, 9): -1, (27, 9): -1, (28, 9): -1, (29, 9): -1, (30, 9): -1, (31, 9): -1, (32, 9): -1, (33, 9): -1, (34, 9): -1, (35, 9): -1, (36, 9): -1, (37, 9): -1, (38, 9): -1, (39, 9): -1, (40, 9): -1, (41, 9): -1, (42, 9): -1, (43, 9): -1, (44, 9): -1, (45, 9): 0, (46, 9): 1, (47, 9): 2, (48, 9): 3, (49, 9): 4, (50, 9): 5, (51, 9): 6, (52, 9): 7, (53, 9): 8, (54, 9): 9, (55, 9): 10, (56, 9): 11, (57, 9): 12, (58, 9): 13, (59, 9): 14, (60, 9): 15, (61, 9): 16, (62, 9): 17, (63, 9): 18, (64, 9): 19, (65, 9): 20, (66, 9): 21, (67, 9): 22, (68, 9): 23, (69, 9): 24, (70, 9): 25, (71, 9): 26, (72, 9): 27, (73, 9): 28, (74, 9): 29, (75, 9): 30, (76, 9): 31, (77, 9): 32, (78, 9): 33, (79, 9): 34, (80, 9): 35, (81, 9): 36, (82, 9): 37, (83, 9): 38, (84, 9): 39, (85, 9): 40, (86, 9): 41, (87, 9): 42, (88, 9): 43, (89, 9): 44, (90, 9): 45, (91, 9): 46, (92, 9): 47, (93, 9): 48, (94, 9): 49, (95, 9): 50, (96, 9): 51, (97, 9): 52, (98, 9): 53, (99, 9): 54, (100, 9): 55, (101, 9): 56, (102, 9): 57, (103, 9): 58, (104, 9): 59, (105, 9): 60, (106, 9): 61, (107, 9): 62, (108, 9): 63, (109, 9): 64, (110, 9): 65, (111, 9): 66, (112, 9): 67, (113, 9): 68, (114, 9): 69, (115, 9): 70, (116, 9): 71, (117, 9): 72, (118, 9): 73, (119, 9): 74, (120, 9): 75, (121, 9): 76, (122, 9): 77, (123, 9): 78, (124, 9): 79, (125, 9): 80, (126, 9): 81, (127, 9): 82, (128, 9): 83, (129, 9): 84, (130, 9): 85, (131, 9): 86, (132, 9): 87, (133, 9): 88, (134, 9): 89, (135, 9): 90, (136, 9): 181, (137, 9): 182, (138, 9): 183, (139, 9): 184, (140, 9): 185, (141, 9): 186, (142, 9): 187, (143, 9): 188, (144, 9): 189, (145, 9): 190, (146, 9): 281, (147, 9): 282, (148, 9): 283, (149, 9): 284, (150, 9): 285}

    def run(self, n, k):
        return self.store[n, k]
if __name__ == '__main__':
    s = Solution()
    if sys.argv[-1] == 't':
        import time
        for d in [[1, 0, 1], [1, 1, 0], [42, 7, 4], [13, 7, -1], [8, 0, 8], [34, 0, 7999], [9, 0, 9], [46, 0, 199999]]:
            r = s.run(d[0], d[1])
            if r != d[-1]:
                print(d, r)
    else:
        for _ in range(int(input())):
            (n, k) = [int(d) for d in input().split(' ')]
            print(s.run(n, k))

Solution (Python):
""""""

def get(n, k):
    if k == 0:
        ans = []
        while n:
            ans.append(min(9, n))
            n -= min(9, n)
        ans = sorted(ans)
        return ''.join([str(x) for x in ans])
    elif k == 1:
        if n < 30:
            ar = [[1, 0], [3, 1], [5, 2], [7, 3], [9, 4], [10, 9], [11, 5], [12, 19], [13, 6], [14, 29], [15, 7], [16, 39], [17, 8], [18, 49], [19, 18], [20, 59], [21, 28], [22, 69], [23, 38], [24, 79], [25, 48], [26, 89], [27, 58], [28, 189], [29, 68]]
            for e in ar:
                if e[0] == n:
                    return e[1]
            return -1
        if n % 2 == 0:
            res = 30
            cur = 289
            add = 100
            while res < n:
                res += 2
                if len(str(cur + add)) > len(str(cur)):
                    add *= 10
                cur += add
            return cur
        else:
            res = 31
            cur = 78
            add = 10
            while res < n:
                res += 2
                if len(str(cur + add)) > len(str(cur)):
                    add *= 10
                cur += add
            return cur
    elif k == 2:
        ar = ([3, 0], [6, 1], [9, 2], [12, 3], [15, 4], [18, 5], [21, 6], [24, 7], [27, 17], [30, 27], [33, 37], [36, 47], [39, 57], [42, 67], [45, 77], [48, 87], [51, 97], [54, 197], [57, 297], [60, 397], [63, 497], [66, 597], [69, 697], [72, 797], [75, 897], [78, 997], [81, 1997], [84, 2997], [87, 3997], [90, 4997], [93, 5997], [96, 6997], [99, 7997], [102, 8997], [105, 9997], [108, 19997], [111, 29997], [114, 39997], [117, 49997], [120, 59997], [123, 69997], [126, 79997], [129, 89997], [132, 99997], [135, 199997], [138, 299997], [141, 399997], [144, 499997], [147, 599997], [150, 699997])
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
    elif k == 3:
        ar = ([6, 0], [10, 1], [14, 2], [15, 9], [18, 3], [19, 19], [20, 8], [22, 4], [23, 29], [24, 18], [25, 7], [26, 5], [27, 39], [28, 28], [29, 17], [30, 6], [31, 49], [32, 38], [33, 27], [34, 16], [35, 59], [36, 48], [37, 37], [38, 26], [39, 69], [40, 58], [41, 47], [42, 36], [43, 79], [44, 68], [45, 57], [46, 46], [47, 89], [48, 78], [49, 67], [50, 56], [51, 189], [52, 88], [53, 77], [54, 66], [55, 289], [56, 188], [57, 87], [58, 76], [59, 389], [60, 288], [61, 187], [62, 86], [63, 489], [64, 388], [65, 287], [66, 96], [67, 589], [68, 488], [69, 387], [70, 196], [71, 689], [72, 588], [73, 487], [74, 296], [75, 789], [76, 688], [77, 587], [78, 396], [79, 889], [80, 788], [81, 687], [82, 496], [83, 989], [84, 888], [85, 787], [86, 596], [87, 1989], [88, 988], [89, 887], [90, 696], [91, 2989], [92, 1988], [93, 987], [94, 796], [95, 3989], [96, 2988], [97, 1987], [98, 896], [99, 4989], [100, 3988], [101, 2987], [102, 996], [103, 5989], [104, 4988], [105, 3987], [106, 1996], [107, 6989], [108, 5988], [109, 4987], [110, 2996], [111, 7989], [112, 6988], [113, 5987], [114, 3996], [115, 8989], [116, 7988], [117, 6987], [118, 4996], [119, 9989], [120, 8988], [121, 7987], [122, 5996], [123, 19989], [124, 9988], [125, 8987], [126, 6996], [127, 29989], [128, 19988], [129, 9987], [130, 7996], [131, 39989], [132, 29988], [133, 19987], [134, 8996], [135, 49989], [136, 39988], [137, 29987], [138, 9996], [139, 59989], [140, 49988], [141, 39987], [142, 19996], [143, 69989], [144, 59988], [145, 49987], [146, 29996], [147, 79989], [148, 69988], [149, 59987], [150, 39996])
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
    elif k == 4:
        ar = [[10, 0], [15, 1], [19, 9], [20, 2], [23, 8], [24, 19], [25, 3], [27, 7], [28, 18], [29, 29], [30, 4], [31, 6], [32, 17], [33, 28], [34, 39], [35, 5], [36, 16], [37, 27], [38, 38], [39, 49], [40, 15], [41, 26], [42, 37], [43, 48], [44, 59], [45, 25], [46, 36], [47, 47], [48, 58], [49, 69], [50, 35], [51, 46], [52, 57], [53, 68], [54, 79], [55, 45], [56, 56], [57, 67], [58, 78], [59, 89], [60, 55], [61, 66], [62, 77], [63, 88], [64, 189], [65, 65], [66, 76], [67, 87], [68, 188], [69, 289], [70, 75], [71, 86], [72, 187], [73, 288], [74, 389], [75, 85], [76, 186], [77, 287], [78, 388], [79, 489], [80, 95], [81, 286], [82, 387], [83, 488], [84, 589], [85, 195], [86, 386], [87, 487], [88, 588], [89, 689], [90, 295], [91, 486], [92, 587], [93, 688], [94, 789], [95, 395], [96, 586], [97, 687], [98, 788], [99, 889], [100, 495], [101, 686], [102, 787], [103, 888], [104, 989], [105, 595], [106, 786], [107, 887], [108, 988], [109, 1989], [110, 695], [111, 886], [112, 987], [113, 1988], [114, 2989], [115, 795], [116, 986], [117, 1987], [118, 2988], [119, 3989], [120, 895], [121, 1986], [122, 2987], [123, 3988], [124, 4989], [125, 995], [126, 2986], [127, 3987], [128, 4988], [129, 5989], [130, 1995], [131, 3986], [132, 4987], [133, 5988], [134, 6989], [135, 2995], [136, 4986], [137, 5987], [138, 6988], [139, 7989], [140, 3995], [141, 5986], [142, 6987], [143, 7988], [144, 8989], [145, 4995], [146, 6986], [147, 7987], [148, 8988], [149, 9989], [150, 5995]]
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
    elif k == 5:
        ar = [[15, 0], [21, 1], [24, 9], [27, 2], [30, 7], [33, 3], [36, 5], [39, 4], [42, 15], [45, 14], [48, 25], [51, 24], [54, 35], [57, 34], [60, 45], [63, 44], [66, 55], [69, 54], [72, 65], [75, 64], [78, 75], [81, 74], [84, 85], [87, 84], [90, 185], [93, 94], [96, 285], [99, 194], [102, 385], [105, 294], [108, 485], [111, 394], [114, 585], [117, 494], [120, 685], [123, 594], [126, 785], [129, 694], [132, 885], [135, 794], [138, 985], [141, 894], [144, 1985], [147, 994], [150, 2985]]
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
    elif k == 6:
        ar = [[21, 0], [28, 1], [30, 9], [32, 8], [34, 7], [35, 2], [36, 6], [37, 19], [38, 5], [39, 18], [40, 4], [41, 17], [42, 3], [43, 16], [44, 29], [45, 15], [46, 28], [47, 14], [48, 27], [49, 13], [50, 26], [51, 39], [52, 25], [53, 38], [54, 24], [55, 37], [56, 23], [57, 36], [58, 49], [59, 35], [60, 48], [61, 34], [62, 47], [63, 33], [64, 46], [65, 59], [66, 45], [67, 58], [68, 44], [69, 57], [70, 43], [71, 56], [72, 69], [73, 55], [74, 68], [75, 54], [76, 67], [77, 53], [78, 66], [79, 79], [80, 65], [81, 78], [82, 64], [83, 77], [84, 63], [85, 76], [86, 89], [87, 75], [88, 88], [89, 74], [90, 87], [91, 73], [92, 86], [93, 189], [94, 85], [95, 188], [96, 84], [97, 187], [98, 83], [99, 186], [100, 289], [101, 185], [102, 288], [103, 184], [104, 287], [105, 93], [106, 286], [107, 389], [108, 285], [109, 388], [110, 284], [111, 387], [112, 193], [113, 386], [114, 489], [115, 385], [116, 488], [117, 384], [118, 487], [119, 293], [120, 486], [121, 589], [122, 485], [123, 588], [124, 484], [125, 587], [126, 393], [127, 586], [128, 689], [129, 585], [130, 688], [131, 584], [132, 687], [133, 493], [134, 686], [135, 789], [136, 685], [137, 788], [138, 684], [139, 787], [140, 593], [141, 786], [142, 889], [143, 785], [144, 888], [145, 784], [146, 887], [147, 693], [148, 886], [149, 989], [150, 885]]
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
    elif k == 7:
        ar = [[28, 0], [36, 1], [37, 9], [38, 8], [39, 7], [40, 6], [41, 5], [42, 4], [43, 3], [44, 2], [45, 19], [46, 18], [47, 17], [48, 16], [49, 15], [50, 14], [51, 13], [52, 12], [53, 29], [54, 28], [55, 27], [56, 26], [57, 25], [58, 24], [59, 23], [60, 22], [61, 39], [62, 38], [63, 37], [64, 36], [65, 35], [66, 34], [67, 33], [68, 32], [69, 49], [70, 48], [71, 47], [72, 46], [73, 45], [74, 44], [75, 43], [76, 42], [77, 59], [78, 58], [79, 57], [80, 56], [81, 55], [82, 54], [83, 53], [84, 52], [85, 69], [86, 68], [87, 67], [88, 66], [89, 65], [90, 64], [91, 63], [92, 62], [93, 79], [94, 78], [95, 77], [96, 76], [97, 75], [98, 74], [99, 73], [100, 72], [101, 89], [102, 88], [103, 87], [104, 86], [105, 85], [106, 84], [107, 83], [108, 82], [109, 189], [110, 188], [111, 187], [112, 186], [113, 185], [114, 184], [115, 183], [116, 92], [117, 289], [118, 288], [119, 287], [120, 286], [121, 285], [122, 284], [123, 283], [124, 192], [125, 389], [126, 388], [127, 387], [128, 386], [129, 385], [130, 384], [131, 383], [132, 292], [133, 489], [134, 488], [135, 487], [136, 486], [137, 485], [138, 484], [139, 483], [140, 392], [141, 589], [142, 588], [143, 587], [144, 586], [145, 585], [146, 584], [147, 583], [148, 492], [149, 689], [150, 688]]
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
    elif k == 8:
        ar = [[36, 0], [45, 1], [54, 11], [63, 21], [72, 31], [81, 41], [90, 51], [99, 61], [108, 71], [117, 81], [126, 91], [135, 191], [144, 291]]
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
    elif k == 9:
        ar = [[45, 0], [46, 1], [47, 2], [48, 3], [49, 4], [50, 5], [51, 6], [52, 7], [53, 8], [54, 9], [55, 10], [56, 11], [57, 12], [58, 13], [59, 14], [60, 15], [61, 16], [62, 17], [63, 18], [64, 19], [65, 20], [66, 21], [67, 22], [68, 23], [69, 24], [70, 25], [71, 26], [72, 27], [73, 28], [74, 29], [75, 30], [76, 31], [77, 32], [78, 33], [79, 34], [80, 35], [81, 36], [82, 37], [83, 38], [84, 39], [85, 40], [86, 41], [87, 42], [88, 43], [89, 44], [90, 45], [91, 46], [92, 47], [93, 48], [94, 49], [95, 50], [96, 51], [97, 52], [98, 53], [99, 54], [100, 55], [101, 56], [102, 57], [103, 58], [104, 59], [105, 60], [106, 61], [107, 62], [108, 63], [109, 64], [110, 65], [111, 66], [112, 67], [113, 68], [114, 69], [115, 70], [116, 71], [117, 72], [118, 73], [119, 74], [120, 75], [121, 76], [122, 77], [123, 78], [124, 79], [125, 80], [126, 81], [127, 82], [128, 83], [129, 84], [130, 85], [131, 86], [132, 87], [133, 88], [134, 89], [135, 90], [136, 181], [137, 182], [138, 183], [139, 184], [140, 185], [141, 186], [142, 187], [143, 188], [144, 189], [145, 190], [146, 281], [147, 282], [148, 283], [149, 284], [150, 285]]
        for e in ar:
            if e[0] == n:
                return e[1]
        return -1
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    print(get(n, k))