TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4463
  • Problem
  • P4463Build a tree
    Limits : Time Limit : 1000 MS   Memory Limit : 565536 KB
    Description

    HazelFan wants to build a rooted tree. The tree has n nodes labeled 0 to n−1, and the father of the node labeled i is the node labeled ⌊(i−1) / k⌋. HazelFan wonders the size of every subtree, and you just need to tell him the XOR value of these answers.

    Input Format

    The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
    For each test case:
    A single line contains two positive integers n,k(1≤n,k≤10^18).

    Output Format

    For each test case:
    A single line contains a nonnegative integer, denoting the answer.

    Sample Input

    2
    5 2
    5 3

    Sample Output

    7
    6


    Source  2017 Multi7 杭州二中