숫자 0과 9로만 이루어진 0 이상의 정수 X가 있다. (ex: 90, 9990, 9009009) 

0이상의 정수 N이 주어졌을 때 X중 N의 배수이면서 가장 작은 수를 구하는 프로그램을 작성하시요. 


입력 

첫줄에 테스트 케이스 T를 입력 받는다. 다음 줄 부터 T줄만큼 N을 입력받는다. 


출력 

각각의 테스트 케이스에 대해서 조건 만족하는 수 X를 한줄에 하나씩 출력한다. 단 숫자 앞에 0이 와서는 안된다. 

(ex: 00999 > 999로 출력할 것) 


제한 

1 <= T <= 104 

1 <= N <= 500


입력 예제 #1

3

5

7

1


출력 예제 #1

90

9009

9


예제 설명 #1

첫번째 테스트 케이스 : 5의 배수이면서 9와 0으로만 이루어진 가장 작은 수는 90이다. 




---------------------------------------------------------------------



4. 주식 투자

당신은 오늘 부터 N일(DAY) 동안의 삼성전자 주가를 예측할 수있는 알고리즘을 개발했다(와우~!!!). 


다만 현재 예산으로는 N일 동안 각각의 날에 다음의 액션중 하나만을 취할 수 있다. 


1) 어떤 날은 삼성전자 주식 1주를 살 수 있다. 

2) 어떤 날은 가지고 있는 주식 중 일부 혹은 전부를 팔 수 있다

3) 어떤 날은 아무런 액션을 취하지 않을 수도 있다. 


N일 뒤에 최고의 수익을 남기기 위해서는 어떠한 전략을 수행해야 하는가? 


입력 

첫 줄에는 테스트 케이스의 수 T를 입력받는다. 

다음에는 숫자 N을 입력한다. 

그 다음 줄에는 N일 동안 예측한 주식의 가격을 입력한다. (모두 정수, 스페이스로 구분) 

이것을 T만큼 반복한다.


출력 

각각의 테스트 케이스에 대해서 최고로 얻을 수 있는 수익을 출력한다. 


제한

1 <= T <= 10 

1 <= N <= 50000


입력 예제 #1

3

3

5 3 2

3

1 2 100

4

1 3 1 2


출력 예제 #1

0

197

3


예제 설명 #1

첫번째 테스트 케이스

주가가 5 > 3 > 2로 떨어지기만 한다. 이래서는 수익을 낼수가 없다. 

두번째 테스트 케이스

1일과 2일에는 1주씩 구매한다. 3일때 모든 주식을 판매한다. 

세번째 테스트 케이스 

1일째 1주를 구매하고 2일째 이 것을 판매한다. 3일째 다시 1주를 구매하고 4일째 판매한다.




자바나 c로 작성해서 제출하라는 문제


답을 알려달라는게 아니고


딱 보면 난이도가 어느정도 수준같음?