시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1958 337 234 19.435%

문제

자연수 N이 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 수 중에서 N과 서로소인 것의 개수를 구하는 프로그램을 작성하시오.

두 정수를 나눌 수 있는 양의 정수가 1밖에 없을 때, 두 정수를 서로소라고 한다. 즉, 두 수의 최대공약수가 1이면 서로소이다. 1은 모든 정수와 서로소이다.

입력

첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109)

출력

각 테스트 케이스마다 A보다 크거나 같고, B보다 작거나 같은 자연수 중에서 N과 서로소인 것의 개수를 출력한다. 

예제 입력 1

2
1 10 2
3 15 5

예제 출력 1

Case #1: 5
Case #2: 10

힌트

[1,10]에 속하는 수 중에서 2와 서로소인 것은 {1, 3, 5, 7, 9}이다.

W3sicHJvYmxlbV9pZCI6IjkzNTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMWNcdWI4NWNcdWMxOGMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIEFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgQlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgTlx1YWNmYyBcdWMxMWNcdWI4NWNcdWMxOGNcdWM3NzggXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIDFcdWJjMTZcdWM1ZDAgXHVjNWM2XHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWMxMWNcdWI4NWNcdWMxOGNcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YjQ1MCBcdWMyMThcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHVhYzAwIDFcdWM3NzRcdWJhNzQgXHVjMTFjXHViODVjXHVjMThjXHVjNzc0XHViMmU0LiAxXHVjNzQwIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMyMThcdWM2NDAgXHVjMTFjXHViODVjXHVjMThjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgwICZsdDsgVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIEEsIEIsIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEgJmxlOyBCICZsZTsgMTA8c3VwPjE1PFwvc3VwPiwgMSAmbGU7IE4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgQVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBCXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBOXHVhY2ZjIFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yzc3OCBcdWFjODNcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+WzEsMTBdXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWMyMTggXHVjOTExXHVjNWQwXHVjMTFjIDJcdWM2NDAgXHVjMTFjXHViODVjXHVjMThjXHVjNzc4IFx1YWM4M1x1Yzc0MCB7MSwgMywgNSwgNywgOX1cdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzU5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ28tcHJpbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkdpdmVuIGEgbnVtYmVyIE4sIHlvdSBhcmUgYXNrZWQgdG8gY291bnQgdGhlIG51bWJlciBvZiBpbnRlZ2VycyBiZXR3ZWVuIEEgYW5kIEIgaW5jbHVzaXZlIHdoaWNoIGFyZSByZWxhdGl2ZWx5IHByaW1lIHRvIE4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlR3byBpbnRlZ2VycyBhcmUgc2FpZCB0byBiZSBjby1wcmltZSBvciByZWxhdGl2ZWx5IHByaW1lIGlmIHRoZXkgaGF2ZSBubyBjb21tb24gcG9zaXRpdmUgZGl2aXNvcnMgb3RoZXIgdGhhbiAxIG9yLCBlcXVpdmFsZW50bHksIGlmIHRoZWlyIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIGlzIDEuIFRoZSBudW1iZXIgMSBpcyByZWxhdGl2ZWx5IHByaW1lIHRvIGV2ZXJ5IGludGVnZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvbiBpbnB1dCBjb250YWlucyBUICgwICZsdDsgVCAmbHQ7PSAxMDApIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgZWFjaCBvZiB0aGUgbmV4dCBUIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIEEsIEIsIE4gd2hlcmUgKDEgJmx0Oz0gQSAmbHQ7PSBCICZsdDs9IDEwPHN1cD4xNTxcL3N1cD4pIGFuZCAoMSAmbHQ7PSBOICZsdDs9IDEwPHN1cD45PFwvc3VwPikuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCB0aGUgbnVtYmVyIG9mIGludGVnZXJzIGJldHdlZW4gQSBhbmQgQiBpbmNsdXNpdmUgd2hpY2ggYXJlIHJlbGF0aXZlbHkgcHJpbWUgdG8gTi4gRm9sbG93IHRoZSBvdXRwdXQgZm9ybWF0IGJlbG93LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgdGVzdCBjYXNlLCB0aGUgZml2ZSBpbnRlZ2VycyBpbiByYW5nZSBbMSwxMF0gd2hpY2ggYXJlIHJlbGF0aXZlbHkgcHJpbWUgdG8gMiBhcmUgezEsMyw1LDcsOX0uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d