시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 612 456 425 75.893%

문제

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

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

입력

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

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

출력

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

예제 입력 1

2
2 1
3 3

예제 출력 1

4
1
W3sicHJvYmxlbV9pZCI6IjExMzIwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGJjXHVhYzAxIFx1YmIzNFx1YjJhYyAtIDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmIzNFx1YzVjN1x1Yzc3NFx1YjRlMCBcdWIzNmVcdWM1YjRcdWJjODRcdWI5YWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWFkNmNcdWMwYWNcdWFjZmNcdWIyOTQgXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgQVx1Yzc3OCBcdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgQlx1Yzc3OCBcdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNjQ0XHVjODA0XHVkNzg4IFx1YjM2ZVx1YzViNFx1YmM4NFx1YjlhY1x1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCZuYnNwO1x1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggQSwgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsJm5ic3A7QiAmbGU7IEEgXHVjNzc0XHVhY2UwLCBBXHViOTdjIEJcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWQ1NWMgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBBXHVjNzc4IFx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM2NDRcdWM4MDRcdWQ1NThcdWFjOGMgXHViMzZlXHVhZTMwIFx1YzcwNFx1ZDU1YywgXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgQlx1Yzc3OCBcdWM4MTVcdWMwYmNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChUJm5ic3A7JmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBBLCBCXHVhYzAwICgxICZsZTsgQiAmbGU7IEEgJmxlOyAxLDAwMCwgQnxBKSZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQ1NWMgXHViY2MwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBBXHVjNzc4IFx1YzgxNVx1YzBiY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWM2NDRcdWJjYmRcdWQ1NThcdWFjOGMgXHViMzZlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNTVjIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAmbmJzcDtCXHVjNzc4Jm5ic3A7XHVjODE1XHVjMGJjXHVhYzAxXHVkNjE1XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExMzIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJpYW5ndWxhdGUgVGhpcyEiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBBIGFuZCBCLCB3aGVyZSBCICZsZTsgQSBhbmQgQiBkaXZpZGVzIEEsIGhvdyBtYW55IGVxdWlsYXRlcmFsIHRyaWFuZ2xlcyBvZiBzaXplIEIgeW91IG5lZWQgdG8gY29tcGxldGVseSBjb3ZlciB0aGUgdHJpYW5nbGUgb2Ygc2l6ZSBBLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIHRlc3QgZmlsZSBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIFQoVCAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy48XC9wPlxyXG5cclxuPHA+RWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdHdvIGludGVnZXJzIEEgYW5kIEIgb24gYSBsaW5lLiAoMSAmbGU7IEIgJmxlOyBBICZsZTsgMSwgMDAwLCBCfEEpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGVxdWlsYXRlcmFsIHRyaWFuZ2xlcyB3aXRoIHNpZGUgQiB0aGF0IGNhbiBjb21wbGV0ZWx5IGNvdmVyIHRoZSBlcXVpbGF0ZXJhbCB0cmlhbmdsZSB3aXRoIHNpZGUgQS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Calgary Collegiate Programming Contest > CCPC 2015 Division 2 B번