곱셈

10진법에서는 6 × 9 = 42가 성립하지 않지만, 13진법에서는 성립한다. 13진법의 42는 4 × 13^1 + 2 × 13^0 = 54이고, 이는 6 × 9의 10진수 값과 같다.

세 정수 p, q, r가 주어진다. 각 정수는 숫자 문자만으로 쓰여 있다. 세 수를 모두 어떤 진법 B(2 ≤ B ≤ 16)의 수로 해석했을 때 p × q = r이 성립하는 B를 찾아라. 가능한 B가 여러 개라면 가장 작은 값을 출력한다.

예를 들어 p = 11, q = 11, r = 121이면 3진법에서 식이 성립한다. 10진법에서도 성립하지만, 가장 작은 올바른 진법은 3이다. 조건을 만족하는 진법이 없으면 0을 출력한다.

첫째 줄에 테스트 케이스의 수 T가 주어진다. 다음 T개의 줄에는 각 테스트 케이스를 나타내는 세 정수 p, q, r가 공백으로 구분되어 주어진다.

p, q, r의 모든 문자는 0부터 9까지의 숫자이다. 10진수 정수로 보았을 때 1 ≤ p, q, r ≤ 1,000,000을 만족한다.

각 테스트 케이스마다 한 줄에 하나의 정수를 출력한다. p × q = r이 성립하는 가장 작은 진법 B를 출력하고, 그런 진법이 없으면 0을 출력한다.