시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 32 0 0 0.000%

문제

상근이는 정수를 0부터 m-1까지의 정수로 매핑시키는 해싱 함수 h(y) = a·y + b mod m를 만들었다. x, n, c, d가 주어졌을 때, 해시값 h(x), h(x+1), ..., h(x+n) 중 몇 개가 구간 [c,d]에 포함되는지 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 105)가 주어진다. 다음 t개 줄에는 a, b, x, n, c, d, m이 주어진다. (1 ≤ m ≤ 1015, c ≤ d < m, a,b < m, x+n ≤ 1015, a·(x+n)+b ≤ 1015)

출력

각 테스트 케이스마다 c ≤ a·(x+i)+b mod m ≤ d 을 만족하는 0 ≤ i ≤ n의 개수를 출력한다.

예제 입력 1

2
2 3 1 3 0 1 7
1 0 0 8 0 8 9

예제 출력 1

1
9
W3sicHJvYmxlbV9pZCI6Ijc2MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NzRcdWMyZjEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTVcdWMyMThcdWI5N2MgMFx1YmQ4MFx1ZDEzMCBtLTFcdWFlNGNcdWM5YzBcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YjllNFx1ZDU1MVx1YzJkY1x1ZDBhNFx1YjI5NCBcdWQ1NzRcdWMyZjEgXHVkNTY4XHVjMjE4IGgoeSkgPSBhJm1pZGRvdDt5ICsgYiBtb2QgbVx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIHgsIG4sIGMsIGRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNTc0XHVjMmRjXHVhYzEyIGgoeCksIGgoeCsxKSwgLi4uLCBoKHgrbikgXHVjOTExIFx1YmE4NyBcdWFjMWNcdWFjMDAgXHVhZDZjXHVhYzA0IFtjLGRdXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdCAoMSAmbGU7IHQgJmxlOyAxMDxzdXA+NTxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIHRcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IGEsIGIsIHgsIG4sIGMsIGQsIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG0gJmxlOyAxMDxzdXA+MTU8XC9zdXA+LCBjICZsZTsgZCAmbHQ7IG0sIGEsYiAmbHQ7IG0sIHgrbiAmbGU7IDEwPHN1cD4xNTxcL3N1cD4sIGEmbWlkZG90Oyh4K24pK2IgJmxlOyAxMDxzdXA+MTU8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IGMgJmxlOyBhJm1pZGRvdDsoeCtpKStiIG1vZCBtICZsZTsgZCBcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IDAgJmxlOyBpICZsZTsgblx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijc2MTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIYXNoaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciB0aGUgaGFzaCBmdW5jdGlvbiBoKHkpID0gYSZtaWRkb3Q7eStiIG1vZCBtIHdoaWNoIG1hcHMgZWFjaCBpbnRlZ2VyIHRvIHNvbWUgaW50ZWdlciBiZXR3ZWVuIDAgYW5kIG0mbWludXM7MS4gWW91IGFyZSBnaXZlbiB4LCBuLCBjLCBkIGFuZCBhcmUgY3VyaW91cyBob3cgbWFueSBvZiB0aGUgaGFzaCB2YWx1ZXMgaCh4KSwgaCh4KzEpLCAuLi4sIGgoeCtuKSBsYW5kIGluIHRoZSBpbnRlcnZhbCBbYywgZF0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgY29udGFpbnMgYSBwb3NpdGl2ZSBpbnRlZ2VyIHQsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyAoMSAmbGU7IHQgJmxlOyAxMDxzdXA+NTxcL3N1cD4pLiB0IGxpbmVzIHRoZW4gZm9sbG93LCB3aGVyZSB0aGUgaXRoIGxpbmUgZ2l2ZXMgdGhlIHZhbHVlcyBhLCBiLCB4LCBuLCBjLCBkLCBtLCBzcGFjZS1zZXBhcmF0ZWQsIGZvciB0aGUgaTxzdXA+dGg8XC9zdXA+IHRlc3QgY2FzZS4gQWxsIGdpdmVuIHZhbHVlcyBhcmUgbm9uLW5lZ2F0aXZlLiBBbHNvLCAxICZsZTsgbSAmbGU7IDEwPHN1cD4xNTxcL3N1cD4sIGMgJmxlOyBkICZsdDsgbSwgYSxiICZsdDsgbSwgeCtuICZsZTsgMTA8c3VwPjE1PFwvc3VwPiwgYW5kIGEmbWlkZG90Oyh4K24pK2IgJmxlOyAxMDxzdXA+MTU8XC9zdXA+LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBpbiBvcmRlciBvdXRwdXQgdGhlIG51bWJlciBvZiBpLCAwICZsZTsgaSAmbGU7IG4sIHN1Y2ggdGhhdCBjICZsZTsgYSZtaWRkb3Q7KHgraSkrYiBtb2QgbSAmbGU7IGQgaW4gdGhhdCB0ZXN0IGNhc2UsIGZvbGxvd2VkIGJ5IGEgbmV3bGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=