Chef has a stick of length L. Chef wants to break the stick into K parts such that each part has a non-zero length. 

Let the lengths of the K parts be A_{1}, A_{2}, \ldots, A_{K} (Note that A_{1} + A_{2} + \ldots + A_{K} = L and A_{i} is a positive integer for all i). Chef wants to minimize the value of \displaystyle \sum_{i = 1}^{K - 1}|A_{i + 1} - A_{i}|. Can you help Chef? (Here |x| denotes the absolute value of x)

Under the given constraints it will always be possible to break the stick into K parts of non-zero lengths.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space-separated integers L and K — the initial length of the stick and the number of parts Chef wants to break the stick into.

------ Output Format ------ 

For each test case, output the minimum value of \displaystyle \sum_{i = 1}^{K - 1}|A_{i + 1} - A_{i}|.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤K ≤L ≤10^{9}$

----- Sample Input 1 ------ 
2
4 3
2 2

----- Sample Output 1 ------ 
1
0

----- explanation 1 ------ 
Test Case 1: It is optimal to break the stick of length $4$ into $3$ parts in the following manner: $[2, 1, 1]$. The value of $\displaystyle \sum_{i = 1}^{K - 1}|A_{i + 1} - A_{i}| = |1 - 2| + |1 - 1| = 1$.

Test Case 2: It is optimal to break the stick of length $2$ into $2$ parts in the following manner: $[1, 1]$. The value of $\displaystyle \sum_{i = 1}^{K - 1}|A_{i + 1} - A_{i}| = |1 - 1| = 0$.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(l, k) = map(int, input().split())
	if l % k != 0:
		print('1')
	else:
		print('0')


for _ in range(int(input())):
	(l, k) = map(int, input().split())
	print(1 if l % k else 0)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	print(1 if N % K else 0)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(l, k) = map(int, input().split())
	if l % k == 0:
		print(0)
	else:
		print(1)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a % b:
		print('1')
	else:
		print('0')


for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(1 if x % y else 0)


n = int(input())
for i in range(n):
	sum = 0
	(L, K) = map(int, input().split())
	if L % K == 0:
		print(0)
	else:
		print(1)


goals = int(input())
for distractions in range(goals):
	(life, wife) = map(int, input().split())
	print(1 if life % wife else 0)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
tc = int(input())
for i in range(tc):
	(vegn, vegx) = map(int, input().split())
	if vegn % vegx == 0:
		print('0')
	else:
		print('1')


t = int(input())
for i in range(t):
	(l, n) = list(map(int, input().split()))
	if l % n == 0:
		print(0)
	else:
		print(1)


try:
	t = int(input())
	for r in range(t):
		a = list(map(int, input().split()))
		x = a[0]
		y = a[1]
		c = x % y
		if c == 0:
			print('0')
		else:
			print('1')
		t -= 1
except:
	pass


for i in range(int(input())):
	(l, k) = map(int, input().split())
	arr = []
	ans = 0
	if l % k == 0:
		print(0)
	else:
		print(1)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	if a % b == 0:
		print('0')
	else:
		print('1')


for j in range(int(input())):
	(p, m) = map(int, input().split())
	if p % m:
		print('1')
	else:
		print('0')


n = int(input())
for _ in range(n):
	(a, d) = list(map(int, input().split()))
	if a % d:
		print('1')
	else:
		print('0')


t = int(input())
i = 1
while i <= t:
	(a, b) = map(int, input().split())
	if a % b == 0:
		print('0')
	else:
		print('1')
	i += 1


for _ in range(int(input())):
	(length, parts) = map(int, input().split())
	rem = length % parts
	if rem == 0:
		print(0)
	else:
		print(1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	if n % m == 0:
		print('0')
	else:
		print('1')


T = int(input(''))
for i in range(T):
	(L, K) = [int(x) for x in input('').split()]
	if L % K == 0:
		print('0')
	else:
		print('1')


t = int(input())
while t:
	(l, k) = map(int, input().split())
	if l % k == 0:
		print(0)
	else:
		print(1)
	t = t - 1


def solve():
	if l % k == 0:
		return 0
	else:
		return 1
for _ in range(int(input())):
	(l, k) = map(int, input().split())
	print(solve())


def breakstick(l, k):
	if l % k == 0:
		print(0)
	else:
		print(1)
for t in range(int(input())):
	(l, k) = map(int, input().split(' '))
	breakstick(l, k)


for i in range(int(input())):
	(l, k) = map(int, input().split())
	res = int(l / k)
	r = l % k
	if r == 0:
		print('0')
	else:
		print('1')


for i in range(int(input())):
	a = [int(x) for x in input().split()]
	x = a[0] % a[1]
	if x == 0:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(1 - int(a % b == 0))


for _ in range(int(input())):
	(L, K) = map(int, input().split())
	if L % K == 0:
		print(0)
	else:
		print(1)