有 N个方块，索引为 0到 (N-1)排列在一条线上。Snuke将通过以下程序来标记每个方格。 标记方格 0. 重复以下步骤i - iii (N-1)次。 初始化一个变量 x有 (A+D)modN，其中 A是上次标记的方块的索引。 当方格 x被标记，重复将 替换为 (x+1)modN。 标记方格 x. 找出Snuke第K次标记的广场的索引。 给出 T个测试案例，找出每个案例的答案。 N,K,D最大均为10^9，给出一个时间复杂度不超时的算法

由于N，K，D的最大值都为10^9，推荐使用高效的循环移位算法来解决这个问题。首先令x=A，令r=0，令m=1，令t=1，令y=0，令z=K；令i=0，令j=1，令k=0；然后，当i<N时，执行以下操作：r=r+m*t，m=m*D，t=t*D，x=x+y，y=y+z，i=i+1，j=j+1，k=k+1，当k=K时，输出索引i。最后，输出索引i即可得到Snuke第K次标记的方格的索引。