You are given two integers n and d. You need to construct a rooted binary tree consisting of n vertices with a root at the vertex 1 and the sum of depths of all vertices equals to d.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a vertex v is the last different from v vertex on the path from the root to the vertex v. The depth of the vertex v is the length of the path from the root to the vertex v. Children of vertex v are all vertices for which v is the parent. The binary tree is such a tree that no vertex has more than 2 children.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

The only line of each test case contains two integers n and d (2 ≤ n, d ≤ 5000) — the number of vertices in the tree and the required sum of depths of all vertices.

It is guaranteed that the sum of n and the sum of d both does not exceed 5000 (∑ n ≤ 5000, ∑ d ≤ 5000).

Output

For each test case, print the answer.

If it is impossible to construct such a tree, print "NO" (without quotes) in the first line. Otherwise, print "{YES}" in the first line. Then print n-1 integers p_2, p_3, ..., p_n in the second line, where p_i is the parent of the vertex i. Note that the sequence of parents you print should describe some binary tree.

Example

Input


3
5 7
10 19
10 18


Output


YES
1 2 1 3 
YES
1 2 3 3 9 9 2 1 6 
NO

Note

Pictures corresponding to the first and the second test cases of the example:

<image>

<image>

Source: codeforces | Difficulty: HARD
Tags: Tree algorithms

Complete search

Constructive algorithms


Solutions:
t = int(input())
import math as m

def print_tree(l):
	t = [{'p': None, 'c': []} for i in range(sum(l))]
	l2 = {i: [] for i in range(len(l))}
	j = 0
	for i in range(sum(l)):
		l2[j].append(i + 1)
		if len(l2[j]) == l[j]:
			j += 1
	for i in range(1, len(l)):
		p = 0
		for n in l2[i]:
			pi = l2[i - 1][p]
			t[n - 1]['p'] = pi
			t[pi - 1]['c'].append(n)
			if len(t[pi - 1]['c']) == 2:
				p += 1
	for i in range(1, len(t)):
		print(t[i]['p'], end=' ')
	print()
for _ in range(t):
	(n, d) = map(int, input().split())
	k = m.floor(m.log2(n))
	maxd = n * (n - 1) // 2
	mind = k * 2 ** (k + 1) - 2 ** (k + 1) + 2 + k * (n - 2 ** (k + 1) + 1)
	if d < mind or d > maxd:
		print('NO')
		continue
	l = [1 for i in range(n)]
	s = maxd
	lowest = 1
	highest = n - 1
	while s > d:
		diff = s - d
		if diff > highest - lowest:
			l[highest] -= 1
			l[lowest] += 1
			s -= highest - lowest
			highest -= 1
			if l[lowest - 1] * 2 == l[lowest]:
				lowest += 1
		else:
			level = highest - diff
			l[level] += 1
			l[highest] -= 1
			s -= diff
	print('YES')
	print_tree(l)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	t = II()
	for _ in range(t):
		(n, d) = MI()
		s = n * (n - 1) // 2
		diff = s - d
		if d > s:
			print('NO')
			continue
		aa = [1] * n
		l = 1
		for r in range(n - 1, -1, -1):
			if l >= r:
				break
			if diff == 0:
				break
			to = max(r - diff, l)
			aa[r] = 0
			aa[to] += 1
			diff -= r - to
			if aa[l] == 1 << l:
				l += 1
		if diff:
			print('NO')
			continue
		ans = []
		pa = 1
		st = 1
		for a in aa[1:]:
			for i in range(a):
				ans.append(st + i % pa)
			st += pa
			pa = a
		print('YES')
		print(*ans)
main()


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	(ld, rd) = (0, n * (n - 1) // 2)
	tn = n
	cd = 0
	mvl = 1
	while tn:
		vl = min(tn, mvl)
		ld += cd * vl
		cd += 1
		tn -= vl
		mvl *= 2
	if not ld <= d <= rd:
		print('NO')
		continue
	parent = [i - 1 for i in range(n)]
	bad = [False] * n
	deep = [i for i in range(n)]
	child = [1] * n
	child[-1] = 0
	cur = rd
	while cur > d:
		v = None
		for i in range(n):
			if not bad[i] and (not child[i]) and (v is None or deep[i] < deep[v]):
				v = i
		p = None
		for i in range(n):
			if child[i] < 2 and deep[i] == deep[v] - 2 and (p is None or deep[i] > deep[p]):
				p = i
		if p is None:
			bad[v] = True
		else:
			child[parent[v]] -= 1
			deep[v] -= 1
			child[p] += 1
			parent[v] = p
			cur -= 1
	print('YES')
	print(*map(lambda x: x + 1, parent[1:]))


import math
import sys
import operator

def raise_d(parent):
	just_parent = [i for (i, j) in parent]
	for deep in range(n):
		if depth_track[-i - 1] >= 2:
			break
	deep_nodes = []
	c = 0
	for (p, depth) in parent[::-1]:
		if depth == deep:
			deep_nodes.append(n - c)
		if len(deep_nodes) == 2:
			break
		c += 1
	for NC in deep_nodes:
		if just_parent.count(NC) < 2:
			(C,) = [x for x in deep_nodes if x != NC]
	parent[C] = (NC, deep + 1)
	depth_track[deep + 1] += 1
	depth_track[deep] -= 1
	return parent
T = int(input())
for _ in range(T):
	(n, d) = map(int, input().split())
	ub = n * (n - 1) // 2
	count = n
	depth = 0
	lb = 0
	while count > 0:
		depth_count = 2 ** depth
		fill = min(count, depth_count)
		count -= fill
		lb += fill * depth
		depth += 1
	if not lb <= d <= ub:
		print('NO')
		continue
	depth_track = [0] * n
	parent = [(-1, -1) for i in range(n + 1)]
	for i in range(1, n + 1):
		if i % 2 == 1:
			p = (i - 1) // 2
			depth = len(bin(i)) - 3
			parent[i] = (p, depth)
			depth_track[depth] += 1
		else:
			p = i // 2
			depth = len(bin(i)) - 3
			parent[i] = (p, depth)
			depth_track[depth] += 1

	def raise_d(parent):
		just_parent = [i for (i, j) in parent]
		for deep in range(n - 1, -1, -1):
			if depth_track[deep] >= 2:
				break
		deep_nodes = []
		c = 0
		for (p, depth) in parent[::-1]:
			if depth == deep:
				deep_nodes.append(n - c)
			if len(deep_nodes) == 2:
				break
			c += 1
		for NC in deep_nodes:
			if just_parent.count(NC) == 0:
				(C,) = [x for x in deep_nodes if x != NC]
				break
		parent[NC] = (C, deep + 1)
		depth_track[deep + 1] += 1
		depth_track[deep] -= 1
		return parent
	for i in range(d - lb):
		parent = raise_d(parent)
	print('YES')
	parent = [p for (p, depth) in parent if depth != 0 and depth != -1]
	print(*parent)


t = int(input())
pows = [2 ** i for i in range(21)]
for _ in range(t):
	(n, d) = map(int, input().split())
	mins = 0
	for k in range(20):
		if pows[k + 1] <= n:
			mins += k * pows[k]
		else:
			mins += k * (n - (pows[k] - 1))
			break
	maxs = n * (n - 1) // 2
	if d < mins or d > maxs:
		print('NO')
	else:
		print('YES')
		ans = [i for i in range(n)]
		cnt = 1
		base = 1
		for i in range(n - 1, -1, -1):
			if maxs - (ans[i] - base) > d:
				maxs -= ans[i] - base
				ans[i] = base
				cnt += 1
				if cnt == pows[base]:
					base += 1
					cnt = 1
			else:
				ans[i] -= maxs - d
				break
		ans = sorted(ans)
		arr = [[] for _ in range(n + 1)]
		for i in range(n):
			arr[ans[i]].append(i + 1)
		ret = []
		for i in range(1, n + 1):
			pos = 0
			cnt = 0
			for j in range(len(arr[i])):
				ret.append(arr[i - 1][pos])
				cnt += 1
				if cnt == 2:
					pos += 1
					cnt = 0
		print(*ret)


import bisect
import sys
input = sys.stdin.readline
t = int(input())
pow2 = [1]
for _ in range(20):
	pow2.append(2 * pow2[-1])
pow2 = set(pow2)
for _ in range(t):
	(n, d) = map(int, input().split())
	p = []
	d0 = []
	now = 0
	(l, l0) = ([1], [1])
	for i in range(2, n + 1):
		p.append(i // 2)
		if i in pow2:
			l.append(i)
			l0.append(i)
			now += 1
		d0.append(now)
	s = sum(d0)
	ans = 'YES' if s <= d <= n * (n - 1) // 2 else 'NO'
	print(ans)
	if ans == 'NO':
		continue
	c = d - s
	for i in range(n, 0, -1):
		if not c:
			break
		if i in pow2:
			continue
		j = bisect.bisect_left(l, i) - 1
		for k in range(j, len(l0) - 1):
			if not c:
				break
			c -= 1
			p[i - 2] = l0[k]
			d0[i - 2] += 1
		if not c:
			break
		c -= 1
		p[i - 2] = l0[-1]
		d0[i - 2] += 1
		l0.append(i)
	print(*p)


for tests in range(int(input())):
	(n, d) = map(int, input().split())
	(upper_bound, lower_bound, lv) = (n * (n - 1) // 2, 0, 0)
	for i in range(1, n + 1):
		if not i & i - 1:
			lv += 1
		lower_bound += lv - 1
	if not d in range(lower_bound, upper_bound + 1):
		print('NO')
	else:
		bad = [False] * n
		depth = list(range(n))
		count_child = [1] * n
		count_child[n - 1] = 0
		current_depth = upper_bound
		parent = list(range(-1, n - 1))
		while current_depth > d:
			v = -1
			for i in range(n):
				if not bad[i] and count_child[i] == 0 and (v == -1 or depth[i] < depth[v]):
					v = i
			if v == -1:
				break
			p = -1
			for i in range(n):
				if count_child[i] < 2 and depth[i] == depth[v] - 2 and (p == -1 or depth[i] > depth[p]):
					p = i
			if p == -1:
				bad[v] = True
				continue
			count_child[parent[v]] -= 1
			depth[v] -= 1
			count_child[p] += 1
			parent[v] = p
			current_depth -= 1
		if current_depth == d:
			print('YES')
			for i in range(1, n):
				print(parent[i] + 1, end=' ')
			print()
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	dsum = n * (n - 1) // 2
	if d > dsum:
		print('NO')
		continue
	tree = [[i] for i in range(n)]
	lmin = 1
	while dsum > d:
		l = len(tree) - 1
		while dsum > d and l > lmin:
			l -= 1
			dsum -= 1
		if l == len(tree) - 1:
			break
		node = tree[-1][-1]
		tree[-1].pop()
		if not tree[-1]:
			tree.pop()
		tree[l].append(node)
		if len(tree[l]) == 2 ** l:
			lmin += 1
	if dsum > d:
		print('NO')
		continue
	print('YES')
	parent = [0] * (n - 1)
	for j in range(1, len(tree)):
		layer = tree[j]
		for i in range(len(layer)):
			node = layer[i]
			parent[node - 1] = tree[j - 1][i // 2] + 1
	print(*parent)


def solve(n, d):
	arr = [[x] for x in range(1, n + 1)]
	S = sum(range(1, n))
	cur = 1
	while S > d and cur != len(arr):
		need = S - d
		can = len(arr) - 1 - cur
		if can < need:
			S -= can
			arr[cur] += arr[-1]
			arr.pop()
		else:
			S -= need
			arr[len(arr) - 1 - need] += arr[-1]
			arr.pop()
		if cur == len(arr):
			break
		elif len(arr[cur]) == 2 ** cur:
			cur += 1
	if S != d:
		print('NO')
	else:
		print('YES')
		ans = [0] * (n - 1)
		for (i, a) in enumerate(arr):
			if i == 0:
				continue
			for (j, v) in enumerate(a):
				ans[v - 2] = str(arr[i - 1][j // 2])
		print(' '.join(ans))
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	solve(n, d)


t = int(input())
for T in range(t):
	(n, d) = map(int, input().strip().split())
	u = (n - 1) * n // 2
	if d > u:
		print('NO')
		continue
	l = t = 0
	for i in range(1, 1 + n):
		l += t
		if not i & i + 1:
			t += 1
	if d < l:
		print('NO')
		continue
	p = [1] * n
	l = [1 << i for i in range(n)]
	o = n - 1
	while u > d:
		m = o
		while u > d and m and (p[m - 1] < l[m - 1]):
			m -= 1
			u -= 1
		p[o] -= 1
		p[m] += 1
		o -= 1
	r = [0] * n
	c = [1, 1]
	t = []
	v = 1
	for i in range(1, n):
		if not p[i]:
			break
		for j in range(p[i]):
			r[v] = c.pop()
			v += 1
			t.append(v)
			t.append(v)
		c = t
		t = []
	print('YES')
	print(*(r[i] for i in range(1, n)))


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, d) = map(int, input().split())
	MIN = sum([i.bit_length() - 1 for i in range(1, n + 1)])
	MAX = (n - 1) * n // 2
	if MIN <= d <= MAX:
		print('YES')
	else:
		print('NO')
		continue
	TREE = [i // 2 for i in range(n + 1)]
	STEM = [1 << i for i in range(n.bit_length())]
	SETSTEM = set(STEM)
	rest = d - MIN
	for x in range(n, -1, -1):
		if x in SETSTEM:
			continue
		if rest == 0:
			break
		now_height = x.bit_length() - 1
		max_height = len(STEM)
		if rest > max_height - now_height:
			rest -= max_height - now_height
			TREE[x] = STEM[-1]
			STEM.append(x)
		else:
			TREE[x] = STEM[now_height + rest - 1]
			break
	print(*TREE[2:])


import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	t = int(input())
	for _ in range(t):
		(n, d) = map(int, input().split())
		depth = [0] + list(range(n))
		child = [0] + [1] * (n - 1) + [0]
		par = [-1, -1] + list(range(1, n))
		cur_d = sum(depth)
		if d > cur_d:
			print('NO')
			continue
		for i in range(n, 0, -1):
			if child[i]:
				continue
			child[par[i]] -= 1
			(p, delta) = (-1, 0)
			for j in range(1, n + 1):
				if i != j and child[j] < 2 and (cur_d - d >= depth[i] - depth[j] - 1) and (depth[i] - depth[j] - 1 > delta):
					delta = depth[i] - depth[j] - 1
					p = j
			if p != -1:
				child[p] += 1
				par[i] = p
				depth[i] = depth[p] + 1
				cur_d -= delta
			else:
				break
		if cur_d == d:
			print('YES')
			print(*par[2:])
		else:
			print('NO')
main()


from math import ceil, floor, log
t = int(input())
for i2 in range(t):
	(n, d) = map(int, input().split())
	(p, dad) = (0, [0] * (n + 1))
	c = n * (n - 1) // 2
	for i in range(1, n + 1):
		p += floor(log(i, 2))
	if p > d or c < d:
		print('NO')
		continue
	now = 1
	dad = [0] * (n + 1)
	vec = [[] for i in range(n + 1)]
	for i in range(1, n + 1):
		vec[i - 1].append(i)
	for i in range(n, 0, -1):
		if c - d <= i - 1 - now:
			vec[now].append(i)
			dad[i] = vec[i - 2 - (c - d)][(len(vec[i - (c - d) - 1]) + 1) // 2 - 1]
			break
		else:
			vec[now].append(i)
			dad[i] = vec[now - 1][(len(vec[now]) + 1) // 2 - 1]
			c -= i - 1 - now
			if len(vec[now]) >= 2 ** now:
				now += 1
	print('YES')
	for i in range(2, n + 1):
		if dad[i] == 0:
			print(i - 1, end=' ')
		else:
			print(dad[i], end=' ')
	print('')


from os import path
from sys import stdin, stdout
if path.exists('inp.txt'):
	stdin = open('inp.txt', 'r')
maxn = 5005
q = int(stdin.readline())
for _ in range(q):
	(n, d) = map(int, stdin.readline().split())
	a = [0 for i in range(maxn)]
	b = [0 for i in range(maxn)]
	use = [0 for i in range(maxn)]
	ans = [0 for i in range(maxn)]
	row = [[] for i in range(maxn)]
	left = int(n * (n - 1) / 2) - d
	pos = n
	for i in range(2, n + 1):
		b[i] = 1
		a[i] = i - 1
	while left and pos >= 2:
		for i in range(1, pos + 1):
			if b[i] > 0 and left >= pos - i:
				left -= pos - i
				a[pos] = i - 1
				b[i + 1] += 2
				b[i] -= 1
				break
		pos -= 1
	if left:
		print('NO')
	else:
		print('YES')
		a = sorted(a[0:n + 1])
		row[0].append(1)
		for i in range(2, n + 1):
			for v in row[a[i] - 1]:
				if use[v] < 2:
					use[v] += 1
					ans[i] = v
					row[a[i]].append(i)
					break
		print(*ans[2:n + 1])


t = int(input())
for loop in range(t):
	(n, d) = map(int, input().split())
	lis = [1] * n
	nsum = 0
	for i in range(n):
		nsum += i
	sub = nsum - d
	if d > nsum:
		print('NO')
		continue
	ableind = 1
	pickind = n - 1
	while pickind > ableind:
		if sub > pickind - ableind:
			lis[pickind] -= 1
			lis[ableind] += 1
			sub -= pickind - ableind
		else:
			lis[pickind] -= 1
			lis[pickind - sub] += 1
			sub = 0
			break
		if lis[ableind] == 2 ** ableind:
			ableind += 1
		if lis[pickind] == 0:
			pickind -= 1
	if sub > 0:
		print('NO')
	else:
		print('YES')
		ans = []
		for i in range(n):
			if i == 0:
				ans.append([1])
				ind = 2
			else:
				nlis = []
				for j in range(lis[i]):
					nlis.append(ind)
					ind += 1
				ans.append(nlis)
		pl = []
		for i in range(1, n):
			for j in range(lis[i]):
				pl.append(ans[i - 1][j // 2])
		print(' '.join(map(str, pl)))