1379와 세제곱

숫자 S가 주어진다. S의 마지막 자리는 1, 3, 7, 9 중 하나이다. 이 조건을 만족하는 S에 대해서는, 어떤 정수 x의 세제곱이 S로 끝나도록 하는 x가 항상 존재한다.

각 테스트 케이스마다 x^3의 끝부분이 S와 같고, x의 십진수 길이가 S의 길이 이하인 정수 x를 하나 찾아 출력하라.

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

다음 T개 줄에는 각 테스트 케이스의 숫자 S가 한 줄에 하나씩 주어진다. S는 1, 3, 7, 9 중 하나로 끝나며, 길이는 최대 10자리이다.

각 테스트 케이스마다 조건을 만족하는 정수 x를 한 줄에 하나씩 출력한다.