Description

数根是将一正整数的各个位数相加(即横向相加)后，若加完后的值大于等于10的话，则继续将各位数进行横向相加直到其值小于十为止所得到的数，即为数根。换句话说，数根是将一数字重复做其数字之和，直到其值小于十为止，则所得的值为该数的数根。例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。

糖糖听到这个道理之后发现很简单啊，所以糖糖想知道等于一个数根的数字有哪些，糖糖开始自己的统计，这时他的同桌茜茜回来了，看到了这些数字对糖糖说我想考考你。茜茜说我告诉你一个数根M，让你来找第N个数的数根为M。作为记忆超群的糖糖（我都不信，emmm）希望自己能快速说出来，所以请你来帮糖糖找出这个数字。

Format

Input

第一行包含一个整数t（1≤t≤10^3） - 茜茜询问次数。接下来的t行包含两个整数N（1≤N≤10^12）和M（1≤M≤9） - 你需要找到第N个正数，其数字根是M 。(在所有等于M数根的数进行从小到大排序后找到的第N个数字）

Output

输出t行，第i行应该包含一个整数 - 第i个问题的答案。

Samples

3
1 5
5 2
3 1

5
38
19

Hint