33615번 - 1과 5 스페셜 저지

1과 5만으로 이루어진 양의 정수 $N$이 주어진다. 이 수에서 원하는 위치의 숫자를 제거하는 연산을 1번 이하로 수행하여 주어진 정수를 합성수로 만드시오. 주어진 수가 이미 합성수라면 숫자를 제거하지 않아도 된다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1\le T\le 10\, 000$)

각 테스트 케이스의 첫째 줄에 양의 정수 $N$이 주어진다. $N$의 길이는 $3$ 이상 $500\,000$ 이하이다.

모든 테스트 케이스에서 $N$의 길이의 합은 $500\, 000$을 넘지 않는다.

각 테스트 케이스의 첫째 줄에 두 개의 정수를 공백을 두고 출력한다.

첫 번째 수는 $N$에서 숫자를 하나 제거한다면 왼쪽에서부터 세었을 때 몇 번째 숫자인지를, 제거하지 않는다면 0을 출력한다.

두 번째 수는 그 결과로 얻어진 수 $N'$의 약수를 하나 출력한다. 이 약수는 $1$보다 크고 $N'$보다 작으며 $10^9$를 초과하지 않아야 한다.

모든 가능한 입력에 대해 조건을 충족하는 출력이 존재함을 증명할 수 있다.