In a country called Chef Land, there was a lot of monetary fraud, so Chefu, the head of the country, decided to choose new denominations of the local currency ― all even-valued coins up to an integer $N$ should exist. After a few days, a citizen complained that there was no way to create an odd value, so Chefu decided that he should also introduce coins with value $1$. Formally, you are given an integer $N$; for $v = 1$ and each even positive integer $v \le N$, coins with value $v$ exist.
You are also given an integer $S$. To handle transactions quickly, find the minimum number of coins needed to pay a price $S$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $S$ and $N$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum number of coins.

-----Constraints-----
- $1 \le T \le 10,000$
- $1 \le S \le 10^9$
- $2 \le N \le 10^9$
- $N$ is even

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
4
2 2
1 14
30 10
31 4

-----Example Output-----
1
1
3
9

-----Explanation-----
Example case 1: One coin with value $2$ is sufficient.
Example case 2: We need to use one coin with value $1$.
Example case 3: We need $3$ coins, each with value $10$.
Example case 4: We can use seven coins with value $4$, one coin with value $2$ and one coin with value $1$.

Difficulty: interview

Starter code:

Solutions:
for i in range(int(input())):
 n,k=list(map(int,input().split()))
 t=0
 if n%2!=0:
  n-=1
  t+=1
 t+=(n//k)
 if n%k!=0:
  t+=1
 print(t)


for i in range(int(input())):
 n,k=map(int,input().split())
 t=0
 if n%2!=0:
  n-=1
  t+=1
 t+=(n//k)
 if n%k!=0:
  t+=1
 print(t)

for i in range(int(input())):
 n,m= map(int,input().split())
 
 c=0
 c+= n//m
 p= n%m
 
 if(p>=1):
  if(p%2==0 or p==1):
   c+=1
   print(c)
  else:
   c+=2
   print(c)
 else:
  print(c)

for t in range(int(input())):
 s,n=map(int,input().split())
 x=0
 if s%2!=0:
  s-=1
  x+=1
 x+=(s//n)
 if s%n!=0:
  x+=1
 print(x)

for _ in range(int(input())):
 s,n= list(map(int,input().split()))
 count=0
 if s>n:
  rem = s%n
  count+= (s//n)
  if rem%2==0: 
   if rem!=0:
     
    count+=1
  else:
   if rem ==1:
    count+=1
   else:
    count+=2
 elif s<n:
  if s%2==0: 
   count+=1
  else:
   if s ==1:
    count+=1
   else:
    count+=2
 else:
  count+=1

 print(count)



for t in range(int(input())):
 s,n=map(int,input().split())
 x=0
 if s%2!=0:
  s-=1
  x+=1
 x+=(s//n)
 if s%n!=0:
  x+=1
 print(x)

# cook your dish here
# cook your dish here
t=int(input())
while t>0:
 s,n=map(int,input().split())
 c=0
 if s<=n:
  if s%2==0:
   print("1")
  elif s==1:
   print("1")
  else:
   print("2")
 else:
  if s%2!=0:
   c+=1
   s-=1
  c+=s//n
  if s%n==0:
   print(c)
  else:
   print(c+1)
 t-=1

# cook your dish here
t=int(input())
while t>0:
 s,n=map(int,input().split())
 c=0
 if s<=n:
  if s%2==0:
   print("1")
  elif s==1:
   print("1")
  else:
   print("2")
 else:
  if s%2!=0:
   c+=1
   s-=1
  c+=s//n
  if s%n==0:
   print(c)
  else:
   print(c+1)
 t-=1

# cook your dish here
for T in range(int(input())):
 s,n = list(map(int,input().split()))
 coins = 0
 
 if (s%2!=0):
  s -=1 
  coins += 1 
 
 coins += (s//n)
 if(s%n!=0):
  coins += 1 
 
 print(coins)
   
  


# cook your dish here
for T in range(int(input())):
 s,n = list(map(int,input().split()))
 coins = 0
 
 if (s%2!=0):
  s -=1 
  coins += 1 
 
 coins += (s//n)
 if(s%n!=0):
  coins += 1 
 
 print(coins)
   
  


# cook your dish here
for _ in range(int(input())):
 S,N=(int(i) for i in input().strip().split())
 coinCount=0
 if(S%2==1):
  S-=1
  coinCount+=1
 coinCount+=S//N
 if(S%N!=0):
  coinCount+=1
 print(coinCount)

t = int(input())
for _ in range(t):
 s, n = map(int,input().split())
 c = 0
 if s == n:
  c = 1
 elif s > n:
  c += s // n
  s = s % n
  if s % 2 == 1:
   c += 1
  if s != 0 and s != 1:
   c += 1
   
 else:
  if s % 2 == 1:
   c += 1
  if s != 0 and s != 1:
   c += 1
  
 print(c)

for _ in range(int(input())):
 s,n = list(map(int,input().split()))
 biggest = (n//2)*2
 coins,balance = divmod(s,biggest)
 if balance == 0 :
  print(coins)
 elif balance == 1 or balance%2==0:
  print(coins+1)
 else :
  print(coins+2)


t = int(input())

for _ in range(t):
 s, n = [int(x) for x in input().split()]
 
 ans = 0
 
 if(s == n):
  ans = 1
 elif(s>n):
  ans += s//n
  s = s%n
  if(s%2 == 1):
   ans += 1
  if(s!=1 and s!=0):
   ans += 1
 else:
  if(s%2 == 1):
   ans += 1
  if(s!=1 and s!=0):
   ans += 1
 
 print(ans)

t = int(input())
for _ in range(t):
 s,n = map(int, input().split())
 if s<n:
  if s==1:
   coins = 1
  elif s%2==0:
   coins = 1
  else:
   coins = 2
 else:
  coins = s//n
  r = s%n
  if r==1:
   coins = coins + 1
  elif r!=0 and r%2==0:
   coins = coins + 1
  elif r%2!=0:
   coins = coins + 2
 print(coins)

# cook your dish here
try:
 for _ in range(int(input())):
  s, n = map(int, input().split())
  if s > n:
   c = s // n
   r = s % n
   if r == 0:
    print(c)
   elif r == 1:
    print(c + 1)
   elif r % 2 == 0:
    print(c + 1)
   else:
    print(c + 2)
  else:
   if s % 2 == 0:
    print("1")
   else:
    if s == 1:
     print("1")
    else:
     print("2")
except:
 pass

# cook your dish here
for _ in range(int(input())):
 s,n = map(int,input().split())
 c = 0
 if s<=n or s==1:
  if s%2==0 or s==1:
   print(1)
  else:
   print(2)
 else:
  while n>0:
   if n > s:
    n = s if s % 2 == 0 else s - 1
   else:
    c+=s//n
    s=s%n
    n=n-2
  print(c+s)

for _ in range(int(input())):
 s, n = list(map(int, input().split()))
 coins = 0
 if s <= n or s == 1:
  coins = (1) if (s % 2 == 0 or s == 1) else (2)
  print(coins)
 else:
  while n > 0:
   if n > s:
    n = s if s % 2 == 0 else s - 1
   else:
    coins += s // n
    s = s % n
    n = n - 2
  print(coins + s)


t=int(input())
for z in range(t):
 s,n=map(int,input().split())
 if(s==1):
  print("1")
  continue
 result=0
 i=0
 result=result+s//(n)
 mod=s%n
 if(mod==0):
  print(result)
  continue
 if(mod%2==0 or mod==1):
  result = result +1
 else:
  result=result+2
 print(result)

t = int(input())

for x in range(0, t):
 s, n = list(map(int, input().split()))

 coin = 0

 if(s > n):
  rem = s%n
  coin += int(s/n)

  if(rem%2 == 0 and rem != 0):
   print(coin + 1)
  elif(rem == 0):
   print(coin)
  elif(rem == 1):
   print(coin + 1)
  elif(rem%2 >= 1):
   print(coin + 2)

 elif(s <= n):        
  if(s%2 == 0):
   print(coin + 1)
  elif(s == 1):
   print(coin + 1)
  elif(s%2 >= 1 and s != 1):
   print(coin + 2)
 



# cook your dish here
t = int(input())
for _ in range(t):
 s, n = map(int, input().split())
 cnt = 0
 curr = n
 while s > 0 and curr != 0:
  cnt += s // curr
  s = s % curr
  curr = (s // 2) * 2
 if s > 0:
  cnt += 1
 print(cnt)

# cook your dish here
t=int(input())
while(t>0):
 t-=1
 s,n=map(int,input().split())
 if(s==1):
  print(1)
  continue
 res=0
 i=0
 res=res + s//n
 m=s%n
 if(m==0):
  print(res)
  continue
 if(m%2==0 or m==1):
  res=res+1
 else:
  res=res+2
 print(res)

# cook your dish here
for i in range(int(input())):
 s,n=list(map(int,input().split()))
 if s>n:
  c=s//n
  r=s%n
  if r==0:
   print(c)
  elif r==1:
   print(c+1)
  elif r%2==0:
   print(c+1)
  else:
   print(c+2)
 else:
  if s%2==0:
   print("1")
  else:
   if s==1:
    print("1")
   else:
    print("2")


for _ in range(int(input())):
 S, N = map(int, input().split())
 c = S // N 
 S %= N 
 if S > 0:
  c += (2 if (S%2 and S>1) else 1)
 print(c)