Educational Codeforces Round 59 [Rated for Div. 2] B. Digital root

r囧r小猫 2022-03-22 07:49 192阅读 0赞

Today at the lesson of mathematics, Petya learns about the digital root.

The digital root of a non-negative integer is the single digit value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.

Let's denote the digital root of xx as S(x)S(x). Then S(5)=5S(5)=5, S(38)=S(3+8=11)=S(1+1=2)=2S(38)=S(3+8=11)=S(1+1=2)=2, S(10)=S(1+0=1)=1S(10)=S(1+0=1)=1.

As a homework Petya got nn tasks of the form: find kk-th positive number whose digital root is xx.

Petya has already solved all the problems, but he doesn't know if it's right. Your task is to solve all nn tasks from Petya's homework.

Input

The first line contains a single integer nn (1≤n≤1031≤n≤103) — the number of tasks in Petya's homework. The next nn lines contain two integers kiki (1≤ki≤10121≤ki≤1012) and xixi (1≤xi≤91≤xi≤9) — ii-th Petya's task in which you need to find a kiki-th positive number, the digital root of which is xixi.

Output

Output nn lines, ii-th line should contain a single integer — the answer to the ii-th problem.

Example

input

Copy

3
    1 5
    5 2
    3 1

output

Copy

5
    38
    19

> 有一个公式，digital root = 1 + ((num - 1) % 9)
> 
> 那么，要想求得第k大的num，把上面这个公式变形一下就可以了。
> 
> 最后得： num = 9 \* K + digital root（K = 0，1，2，3 ......）

#include<iostream>
    #include<queue>
    #include<stack>
    #include<algorithm>
    using namespace std;
    typedef long long LL;
    
    
    int main()
    {
    	LL n,m,j,k,i,T,x;
    	cin>>T;
    	while (T--)
    	{
    		cin>>k>>x;
    		cout<<9*(k-1)+x<<endl;
    	}
    	
    	return 0;
    }