Statement
問題文の言語
길이 인 십진법 수 가 주어진다.
에서 문자를 몇 개 지울 수 있다. 남은 문자들의 순서는 바뀌지 않는다. 남은 문자는 개 이상이어야 한다.
남은 문자를 이어 붙여 만든 수가 의 배수 또는 의 배수가 되도록 하려고 한다. 지워야 하는 문자의 최소 개수를 구하여라. 불가능하다면 을 출력하여라.
남은 문자열은 으로 시작해도 된다. 예를 들어 은 십진법 수 을 나타낸다. 도 과 의 배수이다.
Input
입력은 다음과 같은 형식으로 주어진다.
각 케이스는 다음과 같은 형식으로 주어진다.
는 테스트 케이스의 수이다. 는 길이 의 십진법 수이다.
Output
각 테스트 케이스마다 지워야 하는 문자의 최소 개수를 한 줄에 출력한다. 불가능하면 을 출력한다.
Constraints
- .
- .
- 의 첫 문자는 이 아니며, 모든 문자는 숫자이다.
- 모든 테스트 케이스에 대한 의 합은 이하이다.
Subtasks
Samples
入力例
6
4
1007
3
123
2
11
2
67
1
6
2
10
出力例
1
1
-1
1
0
1
번 케이스에서는 맨 앞의 을 지우면 이 된다. 번 케이스에서는 조건을 만족하는 비어 있지 않은 결과를 만들 수 없다.
번 케이스에서는 문자를 지우지 않아도 된다. 번 케이스에서는 을 지우면 이 남는다.