Smith Numbers

1982년, 앨버트 윌란스키(Albert Wilansky)라는 수학자는 그가 가지고 있던 주소록을 훑어보다가 그의 처제인 H. 스미스(H. smith)의 전화번호에 특이한 속성이 있다는 것을 발견했다. 그 수의 각 자리 숫자 합은 그 수의 소인수 각 자리 숫자의 합과 같았다. 잘 이해가 안 된다면 실제 숫자를 예로 들어서 생각해보자. 스미스의 전화번호는 493-7775였다. 이 수는 다음과 같이 소인수분해할 수 있다.
4937775 = 3 x 5 x 5 x 65837
전화번호의 각 자리 숫자의 합은 4+9+3+7+7+7+5=42이고 소인수의 각 자리 숫자의 합은 3+5+5+6+5+8+3+7=42이므로 둘 다 42로 같은 값을 가진다. 윌란스키는 이런 유형의 수에 처제의 이름을 딴, 스미스 수라는 이름을 붙였다.
모든 소수는 이런 속성을 가지기 때문에 소수는 스미스 수에서 제외되었다. 다른 스미스 수로는 6,036과 9,985 등이 있다.
그런데 윌란스키는 그의 처제의 전화번호보다 큰 스미스 수를 찾지 못했다. 윌란스키를 도와서 그 전화번호보다 큰 스미스 수를 찾을 수 있을까?

첫번째 줄에는 테스트 케이스의 개수가 입력된다. 각 테스트 케이스마다 한 줄씩 입력되며, 그 줄에는 10^9보다 작은 양의 정수가 들어있다.

입력된 각각의 값 n에 대해, n보다 큰 가장 작은 스미스 수를 계산해서 그 정수를 출력한다. 한 줄에 하나씩의 결과를 출력한다. 그러한 정수가 반드시 존재한다고 가정해도 된다.

~cpp 
1
4937774

~cpp 
4937775

작성자	사용언어	개발시간	코드
문보창	C++	60min	SmithNumbers/문보창
이도현	C	3h 20m	SmithNumbers/이도현
신재동	C++	47m	SmithNumbers/신재동
상협	C++	43min	SmithNumbers/남상협
조현태	C	.	SmithNumbers/조현태

----
문제분류 AOI