시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1371 211 132 16.709%

문제

자연수 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+XHViNDUwIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWFjMDAgMVx1YmMxNlx1YzVkMCBcdWM1YzZcdWM3NDQgXHViNTRjLCBcdWI0NTAgXHVjODE1XHVjMjE4XHViOTdjIFx1YzExY1x1Yjg1Y1x1YzE4Y1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHViNDUwIFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWFjMDAgMVx1Yzc3NFx1YmE3NCBcdWMxMWNcdWI4NWNcdWMyMThcdWM3NzRcdWIyZTQuIDFcdWM3NDAgXHViYWE4XHViNGUwIFx1YzgxNVx1YzIxOFx1YzY0MCBcdWMxMWNcdWI4NWNcdWMxOGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQgKDAgJmx0OyBUICZsZTsgMTAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgQSwgQiwgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSAmbGU7IEIgJmxlOyAxMDxzdXA+MTU8XC9zdXA+LCAxICZsZTsgTiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBBXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIEJcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMTggXHVjOTExXHVjNWQwXHVjMTFjIE5cdWFjZmMgXHVjMTFjXHViODVjXHVjMThjXHVjNzc4IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5bMSwxMF1cdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgMlx1YzY0MCBcdWMxMWNcdWI4NWNcdWMxOGNcdWM3NzggXHVhYzgzXHVjNzQwIHsxLCAzLCA1LCA3LCA5fVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzNTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDby1wcmltZSIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBudW1iZXIgTiwgeW91IGFyZSBhc2tlZCB0byBjb3VudCB0aGUgbnVtYmVyIG9mIGludGVnZXJzIGJldHdlZW4gQSBhbmQgQiBpbmNsdXNpdmUgd2hpY2ggYXJlIHJlbGF0aXZlbHkgcHJpbWUgdG8gTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VHdvIGludGVnZXJzIGFyZSBzYWlkIHRvIGJlIGNvLXByaW1lIG9yIHJlbGF0aXZlbHkgcHJpbWUgaWYgdGhleSBoYXZlIG5vIGNvbW1vbiBwb3NpdGl2ZSBkaXZpc29ycyBvdGhlciB0aGFuIDEgb3IsIGVxdWl2YWxlbnRseSwgaWYgdGhlaXIgZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3IgaXMgMS4gVGhlIG51bWJlciAxIGlzIHJlbGF0aXZlbHkgcHJpbWUgdG8gZXZlcnkgaW50ZWdlci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9uIGlucHV0IGNvbnRhaW5zIFQgKDAgJmx0OyBUICZsdDs9IDEwMCkgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBlYWNoIG9mIHRoZSBuZXh0IFQgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgQSwgQiwgTiB3aGVyZSAoMSAmbHQ7PSBBICZsdDs9IEIgJmx0Oz0gMTA8c3VwPjE1PFwvc3VwPikgYW5kICgxICZsdDs9IE4gJmx0Oz0gMTA8c3VwPjk8XC9zdXA+KS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IHRoZSBudW1iZXIgb2YgaW50ZWdlcnMgYmV0d2VlbiBBIGFuZCBCIGluY2x1c2l2ZSB3aGljaCBhcmUgcmVsYXRpdmVseSBwcmltZSB0byBOLiBGb2xsb3cgdGhlIG91dHB1dCBmb3JtYXQgYmVsb3cuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBmaXJzdCB0ZXN0IGNhc2UsIHRoZSBmaXZlIGludGVnZXJzIGluIHJhbmdlIFsxLDEwXSB3aGljaCBhcmUgcmVsYXRpdmVseSBwcmltZSB0byAyIGFyZSB7MSwzLDUsNyw5fS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=