시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 194 92 82 47.399%

문제

무엇이든 덮어버리는 것을 좋아하는 한변의 길이가 A인 정삼각형을 한변의 길이가 B인 정삼각형으로 완전히 덮어 버리고자 한다. 

두개의 정수 A, B 가 주어지고, B ≤ A 이고, A를 B로 나눌수 있을때, 한 변의 길이가 A인 정 삼각형을 완전하게 덮기 위한, 한변의 길이가 B인 정삼각형의 개수를 구하라.

입력

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

각각의 테스트 케이스는 한줄로 이루어져 있으며 두개의 정수 A, B 가 (1 ≤ B ≤ A ≤ 1,000,000, B|A) 주어진다.

출력

각 테스트 케이스마다 한변의 길이가 A인 정삼각형을 완벽하게 덮을 수 있는 한변의 길이가 B인 정삼각형의 최소 개수를 출력한다.

예제 입력

2
2 1
3 3

예제 출력

4
1

힌트