有 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，请给出一个时间复杂度为O(logK)的算法

我可以提供一个时间复杂度为O(logK)的算法：首先，利用二进制表示K，可以将K表示为2^i*K0，其中K0是K的二进制位，i是K的最高位数。然后，可以使用一种称为快速幂的技术，以将D的幂数乘以K0，即D^K0，来确定最终的索引值。时间复杂度为O(logK)。