TopCoder

Thumb f355836eddc451da1b2a1136b7fd5266d216328b
魔法偽娘帕秋莉
想成為帕秋莉的藍孩子

User's AC Ratio

58.3% (7/12)

Submission's AC Ratio

23.3% (10/43)

Description

在C語言當中,迴圈佔有相當重要的地位。
現在讓我們考慮一個這樣子的迴圈:

for(variable = A; variable != B; variable +=C)
  statement;
由於variable是一個用k-bit儲存的無號整數變數,所以只能儲存0到2k-1的整數,
一旦該數字加至2k就會歸零,也就是variable = (variable + C) mod 2k
例如當k=3的時候7+1=0。

現在我們想知道的是,給你一個這樣子的迴圈(A,B,C,k之值),請問這個迴圈裡面的statement會被執行幾次?

Input Format

輸入檔的第一列有一個正整數T,代表接下來的測試資料筆數。
每筆測試資料佔一列包含四個整數A,B,C,k。(1<=k<=32,0<=A,B,C<2k)

Output Format

對於每筆測試資料請輸出迴圈內容(statement)的執行次數,若迴圈永遠不會停下來請輸出"FOREVER"。

Sample Input

4
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16

Sample Output

0
2
32766
FOREVER

Hints

Problem Source

原TIOJ1135 / 96 TWN Practice Contest 1。NTU Judge(problem 0110)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536