CODESPTC  Card Shuffling
Here is an algorithm for shuffling N cards:
 The cards are divided into K equal piles, where K is a factor of N.
 The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the initial pile is the bottom card of pile 1).
 The next N / K cards from the bottom belong to pile 2, and so on.
 Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2,..., the Kth card of the shuffled pile is the top card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.
For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".
Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?
Input
The first line contains the number of test cases T. The next T lines contain two integers each N and K.
Output
Output T lines, one for each test case containing the minimum number of shuffles needed. If the deck never comes back to its original order, output 1.
Constraints
T <= 10000
2 <= K <= N <= 10^9
K will be a factor of N.
Example
Sample Input: 3 6 3 4 2 5 5 Sample Output: 6 4 2
hide comments
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130416 19:37:13
Why my memory usage is 2.6MB? I didn't precompute the value that much. Is SPOJ change the system?


Francky:
20130413 11:03:31
My 200th problem, AC at first try, and first place. I highly recommend this one to all great solvers ;)

Added by:  Varun Jalan 
Date:  20111015 
Time limit:  0.445s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem used for CodeSprint  InterviewStreet Contest 